Originally posted by: Dogdog

Hallo,
I was searching a pareto front for two objectives with Cplex. Intuitively I set one objetive value as a constrain in the model and trying to get the optimal value for another objective. The problem I met is, is there any possibility that I can change the constrain value in every iteration so that I can get some kind of a pareto front line?
thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If by iteration you mean after each new "optimal" solution, that's easy. If by iteration you mean after each pivot, that would be inappropriate.

Another approach is to make the objective a weighted sum of the two criteria (weight between 0 and 1). Start with weight = 0 and optimize. Use the sensitivity information from the objective to determine how much you can increase the weight before the solution changes. Increase it slightly more than that and solve again. Repeat until the next weight would exceed 1. That gets all the corners of the Pareto frontier.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The simplest case is if your two objectives are linear. As Paul pointed out you can formulate your problem as a weighted sum of the two linear objectives:

min  c1'x + w * c2'x
s.t. constraints

then vary w from 0 to a large positive number and resolve the problem for different values of w using CPLEX warm-start techniques to get the Pareto front (efficient frontier).

You can also put one of the objectives into the constraint:

min   c1'x
s.t.  c2'x <= v
      constraints

and resolve varying v to get the efficient frontier. Make sure that you script uses warm-start to speed up the solution time, but the detailed implementation depends on which API you are using (Matlab, C, C++, Java, etc.).

With both formulations you get the approximated Pareto front (as you have discretized w or v ). You can also compute exact piecewise linear Pareto front using second formulation and CPLEX sensitivity analysis routines. In that case, you start with an initial v and compute the endpoints v1 and v2 of the interval for v where the current basis remain optimal. After that you move to the point ( v2 + dv ), where dv is a small number) and compute the new endpoints using CPLEX sensitivity analysis. In the current CPLEX version you cannot use sensitivity analysis with the weighted sum formulation as CPLEX does it only for a single constraint or a single coefficient in the objective, while you need to do it for all coefficients of the vector c2 in the objective to compute w1 and w2 from (c1'x + w * c2'x).

If at least one of your objectives is not linear, but convex quadratic, you cannot use CPLEX sensitivity analysis as it is available for linear optimization problems only. In that case you just compute approximate Pareto front using one of the two formulations (weighted sum formulation of v -constrained formulation) and discretizing w or v.

Alternative way to solve bi-objective optimization problem is to use parametric optimization techniques. You can call CPLEX from Yalmip to produce Pareto fronts with parametric optimization.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: K N Reddy

Can I get some references for weighted sum method which explained above?? Is it correct format or below one is correct

Min w1*c1'x+w2*c2'x

S.to. Constraints and

w1+w2=1

 

Please clarify me in this regard.

 

Thanks in advance

 

 

#CPLEXOptimizers
#DecisionOptimization

Assuming you constrain w1 and w2 nonnegative, your approach is fine. It is nearly equivalent to the previous approach (setting the previous w to your w2/w1). The only difference is that your approach allows assigning a zero weight to the first objective (which is appropriate for finding one anchor of the Pareto frontier). In the other approach, you start by optimizing the first objective alone, then use sensitivity to decide new values for w.

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: K N Reddy

Thanks PaulRubin,

But, I didn't find previous approach in literature. So, I asked is there any references are there.

#CPLEXOptimizers
#DecisionOptimization

Probably ... but I don't know any off-hand. Try searching jointly for "LP" and "Pareto frontier".

#CPLEXOptimizers
#DecisionOptimization