Two-Objective Optimization in CPLEX

Question

Until now, I used CPLEX to solve single-objective optimization problems only, but now I need to solve a two-objective mixed-integer linear optimization problem and I noticed that CPLEX 12.6.9 (unlike its previous versions) is able to accomplish this.

So, I'm wondering about two questions:

1. Which algorithm does CPLEX use to solve two-objective problems?

Maybe this piece of text (copied from CPLEX Official Page) could answer my question..

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.

2. What are the main advantages/disadvantages between, solving a two-objective optimization problem:

   a) by passing it directly as a two-objective problem to CPLEX, or

   b) by solving it, in CPLEX, by adopting the "Augmented Epsilon-Constraint Method"?

I guess that a) could allow writing less code, but I don't know anything about differences in terms of efficiency, computational time, etc.

Moreover, I'm wondering if these two methods may generate different solutions.

Answer 1

The augmented $\varepsilon$-constraint method is designed to generate all non-dominated outcome vectors to a bi-objective (or multi objective) optimization problem, whereas a lexicographic optimization approach is designed to generate one particular non-dominated outcome vector to bi-objective (or multiobjective) problem. So it all depends on what you want to achieve. Given that a lexicographic optimal solution is one among many efficient solutions one should expect that using an $\varepsilon$-constraint method to generate all efficient solutions is computationally much harder than just finding a lexicographic optimum. To explicitly address your last question : a) gives you one solution and b) gives you a set of solutions.

Answer 2

As Sune noted, the $\epsilon$-constraint method is not comparable to what CPLEX does, since it finds all Pareto efficient solutions. In case you were thinking of option 2 as finding a lexicographic optimum by optimizing the highest priority objective, constraining it to be optimal, optimizing the next highest priority objective etc. (similar to but not the same as the $\epsilon$-constraint method), I would expect CPLEX's version to be more efficient.

Disclaimer: What follows is conjecture, since I'm not privy to the internal workings of CPLEX. CPLEX maintains a solution pool (feasible but not necessarily optimal solutions encountered along the way). By dropping solutions from the pool only when they are lexically dominated by a new solution, it can in effect get a head start on each subsequent objective (using the pool solution with the best value of that objective as an incumbent). Also, it can modify the rules for pruning nodes so that a node is pruned only if the bound is strictly inferior to the best known value of the highest priority goal. Not pruning nodes where the bound ties the best known value (or removing them from the current search tree and adding them to a "shadow" tree for later searching) allows it to come back later, when it has finished optimizing the first objective, and search for nodes that match the optimal value of the first objective and improve on the second (or subsequent) objective without wandering through parts of the original search tree that were ruled out.