Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  Refreshing the coefficients of the objective function

    Posted 08/11/13 06:00 AM

    Originally posted by: ostaz


    Hello everyone,

    I am programming the Benders decomposition for the network design problem with multicommodity flow.

    In a Benders decomposition framework, the problem is decomposed into a master problem(involving capacities on the link) and a sub problem (involving routing the commodities according to the capacity vector of the master problem).

    I start solving the sub problem, that generates constraints which are added to the master problem, in an iterative manner. The mastre problem returns an array (lambda) which components (cap[i]) are the coefficients of the objective function of the sub problem. Here cap[i] is an array to get back the values of the solution of master problem lambda[i].

    Note that the objective finction of the mastre problem does not change.

    The problem is that after getting back the optimal solution of the master problem (cap[i]), and putting it into the objective function of the sub problem, cplex does not take into account the new values of cap[i].

    So how to update the coefficients of the objective function of the sub problem?

     

    Please find below important lines of my code in cplex concert with C++

          IloModel MP (env);
          IloNumArray sigm(env, nbCommodities, 0, 10000, ILOFLOAT);
          IloNumArray metr(env, nbEdges, 0, 10000, ILOFLOAT);
          IloNumVarArray lambda(env, nbEdges, 0, 10000, ILOINT);
          
          /Define the objective function of the mastre problem
          IloExpr MPobj = IloSum(lambda);
          MP.add(IloMinimize(env, MPobj));
          MPobj.end();
     
          //Define the subproblem PS
            IloModel PS (env);
            IloNumVarArray mu(env, nbEdges, 0, IloInfinity, ILOFLOAT);
            IloNumVarArray sigma(env, nbCommodities, 0, IloInfinity, ILOFLOAT);
         
          //constraints of PS
           for(j = 0; j < nbCommodities; j++) 
            {
             IloExpr u(env);
             for(i = 0; i < nbEdges; i++)
             {
                u += sz[j]*route[j][i]*mu[i];
                }
             PS.add(u >= sigma[j]);
             u.end();
            }
     
            for(i = 0; i < nbEdges; i++)
                PS.add(mu[i]<=1);
             
          //Objective function of PS  
          IloExpr obj = IloSum(sigma);
            for(i = 0; i < nbEdges; i++)
            {
                obj += -4*IloScalProd(cap, mu);
            }
            PS.add(IloMaximize(env, obj));
            
    IloCplex cplex_PS(env);
    cplex_PS.extract(PS);

    while (cplex_PS.solve() !=0)

    {

     
    while (shortest_path_exists=True)

    {

    check whther there is a better shortest path for any commodity by Dijkstra algorithm;

    generate_constraint of the shortest path;

    add_constraint to the PS;

    PS.solve()

    //getting back the values of sigma and mu in order to generate constraints to the MP

    for (i=0; i<nbCommodities;i++)
                sigm[i]=cplex_PS.getValue( sigma[i]);

    for (j=0; j<nbEdges;j++)

                metr[j]=cplex_PS.getValue( mu[j]);
                cplex_PS.out() <
     

    }

    //Constraints of the MP

        IloExpr v(env);
        IloExpr u(env);
     
        for(i = 0; i < nbCommodities; i++)
           v += sigm[i];
        for(j = 0; j < nbEdges; j++)
           u += 4*metr[j]*lambda[j];
     
       MP.add(v <= u);
        v.end();
        u.end();
     
        IloCplex cplex_MP(env);
        cplex_PMR.extract(MP);
     
      
        cplex_MP.solve();

     

    for (i=0;i<nbEdges;i++)

    {

    cap[i]=cplex_MP.getValue( lambda[i]);

    }

     

    } //of the loop while cplex_PS.solve())

          
     

    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Refreshing the coefficients of the objective function

    Posted 08/12/13 02:28 AM

    Not sure I did understand your problem. Are you saying that this piece of code

    //Objective function of PS  
    IloExpr obj = IloSum(sigma);
    for(i = 0; i < nbEdges; i++)
    {
       obj += -4*IloScalProd(cap, mu);
    }
    PS.add(IloMaximize(env, obj));

    Does not take into account the updated values of cap[]? Could you print out cap[] to make sure its values actually changed? Could you print out 'obj' to see whether it looks as expected? Do you really need this loop? Shouldn't IloScalProd be enough?

    Or do you assume that just assigning to cap[i] should change the objective function in PS? That assumption would not be true. In order to change coefficients in an objective function you can for example use IloObjective::setLinearCoef():

    // Replace 'PS.add(IloMaximize(env, obj));' by
    IloObjective PS_obj = IloMaximize(env, obj);
    ...
    // Update the objective with cap[i]:
    for (i=0;i<nbEdges;i++) {
       cap[i]=cplex_MP.getValue( lambda[i]);
       PS_obj.setLinearCoef(mu[i], cap[i]);
    }

    I also noticed this statement in your code:

    while (shortest_path_exists=True)

    This will always be true since you are using assignment instead of comparison (don't you get a warning from your compiler?). Maybe this is part of the issue?


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Refreshing the coefficients of the objective function

    Posted 08/12/13 04:31 PM

    Originally posted by: ostaz


    Thank you for your valuable advice. It works now!

    In fact, I do need PS_obj.SetLinearCoef in order to update the coefficients of the objective function.

    Thanks a lot


    #CPLEXOptimizers
    #DecisionOptimization


Related Content