Multi-objective Optimization

In real-world applications and decision-making systems, there is often more than one objective to optimize. For example, in supply chain management, one may aim to minimize inventory cost while maximizing order fulfillment rate. COPT provides multi-objective optimization functionality to properly balance the priorities or weights of multiple objectives, using either a hierarchy method or a weighted-sum method, to achieve optimal decisions under multi-objective scenarios.

Modeling Multiple objectives

COPT currently supports linear objective functions. The API function Model.setObjectiveN() is used to define them.

When constructing multi-objective functions, the following key objective parameters must be specified:

  • MultiObjPriority

    The priority of the objective in multi-objective optimization. Higher values indicate higher priority. This determines the order of optimization in hierarchy method.

    Default value 0.0

  • MultiObjWeight

    The weight of the objective in multi-objective optimization. This defines the coefficient of the objective in the weighted-sum method.

    Default value 1.0

  • MultiObjAbsTol

    The absolute tolerance allowed for degradation for the specified objective in multi-objective optimization.

    COPT optimizes objectives sequentially based on their priority: In multi-objective MIP, if the current objective’s optimal value is z, the solution is allowed to degrade z by at most MultiObjAbsTol in subsequent groups. In multi-objective (continuous) LP, this parameter applies to variables. To maintain solution quality of higher-priority objectives, COPT fixes some variable values from the previous optimal solution based on reduced cost. These fixed variables are allowed to violate dual feasibility within the tolerance of MultiObjAbsTol.

    Default value 1e-6

  • MultiObjRelTol

    The relative tolerance allowed for degradation for the specified objective in multi-objective optimization.

    COPT optimizes objectives sequentially based on their priority: In multi-objective MIP, if the current objective’s optimal value is z, subsequent optimization phases allow its objective value to deviate within MultiObjRelTol * |z|. In multi-objective (continuous) linear programming, the degradation is controlled by MultiObjAbsTol, and MultiObjRelTol is ignored.

    Default value 0.0

Notes

  • The above parameters apply only to multiple objectives.

  • When specifying a multi-objective function with setObjectiveN, in addition to specifying the above parameters, the objective index, objective expression, and optimization sense can also be specified.

Following are operations on multi-objective parameters (e.g. COPT Python API):

  1. Use Model.setObjParamN(idx, paramname, newval) to set the parameter of a specific objective function by index.

  2. Use Model.getObjParamN(idx, paramname) to retrieve the value of a parameter for a specific objective function by index.

  3. Use Model.resetObjParamN(idx) to reset the parameters of a specific objective function to its default value.

Solving Multiple objectives

When solving multi-objective models, COPT supports two methods: hierarchy method and weighted-sum method.

Hierarchy Method

The hierarchy method optimizes objectives in descending order of priority. COPT solves each objective while ensuring that the quality of higher-priority objectives is not degraded.

Users can specify priorities while calling Model.setObjectiveN or using Model.setObjParamN to assign a priority to the specified objective. The default priority of each objective is 0.0.

Assuming a model with two objectives, \(obj_1\) and \(obj_2\), with priorities 3 and 2 respectively, COPT will first solve the problem for \(obj_1\), and then solve for \(obj_2\) within the allowable degradation defined for \(obj_1\).

Weighted-sum Method

For objectives with the same priority, COPT uses the weighted-sum method to combine them into a single objective using the specified weights. Weights can be set while calling Model.setObjectiveN or using Model.setObjParamN. The default weight of each objective is 1.0.

Assuming a model includes two objectives at the same priority level: \(\text{min}\ f_1(x)\) and \(\text{min}\ f_2(x)\), with weights \(w_1\) and \(w_2\) respectively. Then, COPT constructs the combined objective below:

(48)\[\min\ w_1 \cdot f_1(x) + w_2 \cdot f_2(x)\]

Note:

  • Please be cautious when assigning a negative weight, as it effectively changes the optimization direction.

  • Avoid assigning excessively large or small weights. A large weight may cause numeric instability, while a small weight may result in an insignificant contribution, potentially ignored due to objective degradation tolerances.

COPT also supports combining the hierarchy method and weighted-sum method together. Each objective can have different/same priority and weight. Objectives are grouped and solved sequentially by priority. Within the same priority group, objectives are combined using the weighted-sum method.

Consider a multi-objective model with four objectives:

(49)\[\begin{split}\begin{aligned} &\min\ \text{obj}_1 = f_1(x) && \text{(priority = 2,\ weight = 1.0)} \\ &\max\ \text{obj}_2 = f_2(x) && \text{(priority = 1,\ weight = 2.5)} \\ &\max\ \text{obj}_3 = f_3(x) && \text{(priority = 1,\ weight = 1.5)} \\ &\min\ \text{obj}_4 = f_4(x) && \text{(priority = 0,\ weight = 1.0)} \\ \end{aligned}\end{split}\]

COPT will first group the objectives by priority (2, 1, 0), and solve them in descending order. For objectives with the same priority, a weighted sum will be used.

Priority = 2:

(50)\[\min\ f_1(x)\]

Priority = 1:

(51)\[\max\ 2.5 \cdot f_2(x) + 1.5 \cdot f_3(x)\]

Priority = 0:

(52)\[\min\ f_4(x)\]

Objective degradation tolerance

When using the hierarchy method for multi-objective optimization, the degree to which a lower-priority objective is allowed to degrade for higher ones can be adjusted via two parameters: MultiObjRelTol (relative degradation tolerance) and MultiObjAbsTol (absolute degradation tolerance).

1.MIP Model

For MIP models, we suppose an objective \(\min\ z_1\) has an optimal value \(v\), and the corresponding MultiObjAbsTol = e. Then, when optimizing the next lower-priority objective \(\min\ z_2\), COPT searches for the optimal solution of \(z_2\) within the feasible region defined by \(z_2 \leq v + e\).

For MIP models, we suppose an objective \(\min\ z_1\) has an optimal value \(v\), and the corresponding MultiObjRelTol = q. Then, when optimizing the next lower-priority objective \(\min\ z_2\), COPT searches for the optimal solution of \(z_2\) within the feasible region defined by \(z_2 \leq v + q*|v|\).

Note: If both relative and absolute tolerances are set for an objective, COPT will use the larger one of the two allowed degradation tolerance.

2.LP Model

For continuous LP models, in order to maintain the quality of higher-priority objectives, COPT fixes certain variables to their optimal values obtained in the previous priority group. Whether a variable is fixed will be determined by whether its reduced cost remains within the MultiObjAbsTol range from violating dual feasibility.

Note: MultiObjRelTol is ignored in LP models.

Retrieving the results of multiple objectives

The optimization results of the multi-objective model can be queried via Model.getAttrN(idx, attrname) (taking COPT-Python API as an example, other interfaces work the same way).

  • idx: The index of the objective.

  • attrname: The attribute name of the objective.

Supported attributes for multiple objectives include: HasQObj, HasNLObj, LpObjval, BestObj, ObjSense, ObjConst.