Topic
  • 2 replies
  • Latest Post - ‏2011-03-02T22:28:51Z by SystemAdmin
Dogdog
Dogdog
1 Post

Pinned topic Make a script to get a pareto line?

‏2011-02-28T12:13:36Z |
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.
Updated on 2011-03-02T22:28:51Z at 2011-03-02T22:28:51Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Make a script to get a pareto line?

    ‏2011-03-01T23: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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Make a script to get a pareto line?

    ‏2011-03-02T22:28:51Z  
    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)
    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.
    Updated on 2014-03-25T01:05:49Z at 2014-03-25T01:05:49Z by iron-man