Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  Problems with obtaining the dual values

    Posted 10/30/18 07:31 AM

    Originally posted by: Joce22


    Hi,

     

    I am new to cplex and I want to use cplex to solve the linear relaxation of the restricted master problem (RMP)  for a branch and price procedure. However, I am having some difficulties with extracting the dual values from the rmp. The initial model in lp format is in the attached. Below is the code where I initialised the model and subsequently added one new column to the model (as I only let my code to loop through twice and obtained 2 sets of dual values).

     

    try {
    IloModel model(env);
     
    IloNumVarArray route(env); // variables
    IloObjective obj = IloMaximize(env); // obj function
    IloRangeArray constraints(env); // N+1 constraints
     
    constraints.add(IloRange(env, -IloInfinity, 4)); // number of providers
    for (int i = 1; i <= N; i++) {
    constraints.add(IloRange(env, -IloInfinity, 1));
    }
     
    for (size_t i = 0; i != routeset.size(); i++) {
    IloNumColumn column = obj(routeprofit[i]);
    column += constraints[0](1);
    for (int j = 1; j <= N; j++) {
    column += constraints[j](vertexpathvisit[j][i]);
    }
    IloNumVar var(column, 0, 1);
    route.add(var);
    column.end();
    }
     
    model.add(constraints);
    model.add(obj);
     
    IloCplex cplex(model);
    cplex.exportModel("model.lp");
     
    // solve pricing problem
    vector<int> bestpathseq;
     
    for (int j = 0; j<2; j++) { // loop through twice 
    if (!cplex.solve()) {
    env.error() << "Failed to optimize LP." << endl;
    throw(-1);
    }
    for (int i = 0; i <= N; i++) {
    modi_profit[i] = profit[i] - cplex.getDual(constraints[i]);
    //cout << " " << cplex.getDual(constraints[i]) << endl;
    }
    env.out() << "Solution value = " << cplex.getObjValue() << endl;
    if (solve_priceproblem(modi_profit, bestpathseq) < 0) break;
     
    IloNumColumn column = obj(profit_bestpath);
    column += constraints[0](1);
    for (int j = 1; j <= N; j++) {
    column += constraints[j](vertexpathvisit[j][routeprofit.size() - 1]);
    }
    IloNumVar var(column, 0, 1);
    route.add(var);
    column.end();
    }
    }

    At the first iteration, I obtained the dual values from cplex and used it to solve the pricing problem where a new decision variable x51 will be created with a coefficient of 270 in the objective function.

    At the second iteration, the dual values given by the cplex do not seem to be correct. I think it has something to do with using devex in the second iteration. This is because the dual values obtained (if I were to sum them all up) correspond to the objective value given by devex instead of the objective value given by cplex.getObjValue(). May I know what devex is, and why the objective value given by devex is different from the objective value given by cplex.getObjValue() (in the output.png file). I am not sure if I am making myself clear but will appreciate a lot if anyone can help to answer my question. Thank you!

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Problems with obtaining the dual values

    Posted 10/31/18 12:59 AM

    Originally posted by: BoJensen


    Hi,

     

    I am not sure I completely understand your problem.

     

    In particular I don't understand :

     

    "This is because the dual values obtained (if I were to sum them all up) correspond to the objective value given by devex instead of the objective value given by cplex.getObjValue()."

     

    You get an unexpected objective ?

     

    Devex is a strategy within simplex and irrelevant for this issue.

     

    The problem you attached has 50 variables and an optimal objective value of 160, so I assume this is the first problem you solve and not the problematic second one.

     

    May I suggest the following debug approach :

     

    1) For each solved problem write out the model to a file before solving.

    2) Check the model is correct (new variable is added correctly).

    3) Solve.

    4) Write out the solution to a solution file.

    5) Compare model file and solution file with the numbers obtained in the cpp code. Check the dual solution compared to the solution file.

     

    If in doubt use the interactive cplex prompt to read in the problem and solve to double check. Here you can also check the solution quality with 'disp sol qual'.

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Problems with obtaining the dual values

    Posted 10/31/18 11:06 AM

    Originally posted by: Joce22


    Thank you for replying,

     

    Can I just check with you lets say I have an initial model coded out initially, for instance these few lines:

    try {
    IloModel model(env);
     
    IloNumVarArray route(env); // variables
    IloObjective obj = IloMaximize(env); // obj function
    IloRangeArray constraints(env); // N+1 constraints
     
    constraints.add(IloRange(env, -IloInfinity, 4)); // number of providers
    for (int i = 1; i <= N; i++) {
    constraints.add(IloRange(env, -IloInfinity, 1));
    }
     
    for (size_t i = 0; i != routeset.size(); i++) {
    IloNumColumn column = obj(routeprofit[i]);
    column += constraints[0](1);
    for (int j = 1; j <= N; j++) {
    column += constraints[j](vertexpathvisit[j][i]);
    }
    IloNumVar var(column, 0, 1);
    route.add(var);
    column.end();
    }
     
    model.add(constraints);
    model.add(obj);
     
    IloCplex cplex(model);
    cplex.exportModel("model.lp");
     
    // solve pricing problem
    vector<int> bestpathseq;
     
    for (int j = 0; j<2; j++) {
    if (!cplex.solve()) {
    env.error() << "Failed to optimize LP." << endl;
    throw(-1);
    }

     

    where the objective and constraints are already added to the model, the model is extracted to cplex and I have called cplex.solve() once.

     

    Subsequently, when I want to add a new column into the model, for instance the following lines:

    IloNumColumn column = obj(profit_bestpath);
    column += constraints[0](1);
    for (int j = 1; j <= N; j++) {
    column += constraints[j](vertexpathvisit[j][routeprofit.size() - 1]);
    }
    IloNumVar var(column, 0, 1);
    route.add(var);
    column.end();

     

    is there a need for me to add the following lines again: 

    model.add(constraints); model.add(obj); cplex.extract (model);

    before calling cplex.solve()?

     

    Thank you!

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: Problems with obtaining the dual values

    Posted 11/02/18 12:30 PM

    You must not add constraints or objective again (this will result in parallel constraints and more than one objective).

    Calling extract() again is optional and redundant. Your code looks correct to me. By the way, you can easily check whether the code behaves as expected by using IloCplex::exportModel() to export the model to an LP file and then check whether after the modification the model looks as expected.


    #CPLEXOptimizers
    #DecisionOptimization


Related Content