Solving multiple objective problems
Explains how to solve a multiple objective problem.
The CPLEX multiobjective optimization algorithm sorts the objectives by decreasing priority value. If several objectives have the same priority, they are blended in a single objective using the weight attributes provided. As a result, CPLEX constructs a sorted list of objectives (or blended objectives), each with a unique priority. CPLEX can then proceed to find the lexicographically minimal (or maximal) solution for this order.
To obtain this solution, each objective is optimized in turn by decreasing order of the priority value in a hierarchical manner. Whenever the optimal solution for an objective (or blended objective) is found, CPLEX imposes that, for the remaining (lower priority) objectives, the only solutions considered are those that are also optimal for the previously (higher priority) optimized objectives. All solution values, including primal and dual variables, reduced costs, as well as primal and dual feasibility status, correspond to the solution of the last subproblem that has been solved.
The two attributes AbsTol and RelTol relax the requirement that
in each step the objective is optimized among the solutions that are optimal to the previous
optimization problems. More precisely, for each objective AbsTol and
RelTol specify, in absolute and relative terms, the maximum deviations allowed from
the optimal value of that objective. However, the meaning of the relaxation of the objective depends
on whether the multiobjective problem is an LP or MIP.
MIP
The relative or absolute deviation is incorporated into a constraint on the associated objective. Leaving these values at their defaults of 0 implies restricting the next optimization to only consider solutions from the optimal set from the previous optimization.
LP
For LPs, CPLEX uses a typically faster method involving reduced cost fixing to enforce lexicographic multiobjective optimization. This alters the meaning of the absolute and relative tolerances. The absolute tolerance defines the threshold for reduced costs above which nonbasic variables in the associated LP solve will be fixed at the bound at which they reside. This typically will be a relatively small value like the optimality tolerance (whose default is 1e-6). It is used to define a meaningful value that defines a significant reduced cost in the context of the multiobjective model (in contrast to the meaningful reduced cost defined by the optimality tolerance, which is for a single LP solve). Given this interpretation, the relative tolerance has no meaningful definition and is not used.