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.
Topic

Re: Make a script to get a pareto line?
20110301T23:27:09ZThis is the accepted answer. This is the accepted answer.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) 
Re: Make a script to get a pareto line?
20110302T22:28:51ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20110301T23:27:09Z
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)
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 warmstart 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 warmstart 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 biobjective optimization problem is to use parametric optimization techniques. You can call CPLEX from Yalmip to produce Pareto fronts with parametric optimization.Updated on 20140325T01:05:49Z at 20140325T01:05:49Z by ironman