Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
Back to discussions
Expand all | Collapse all

adding relaxed optimality cuts

  • 1.  adding relaxed optimality cuts

    Posted 04/22/13 11:23 PM

    Originally posted by: Hosssein


    Hi,

    I am using cp.next() in an optimization problem. As I know cp.next(), after finding a better solution with objective value Z*, imposes a new constraint (Objective Function <Z*) (assuming a minimization problem). Since I am using CP optimizer to solve the subproblem of a column generation model, I am not necessary looking for the optimal solution and solution with good negative reduced cost are ok to me. So, this new optimality cut (Objective Function <Z*) is not appropriate to me and I want to apply a relaxed version of this cut like (Objective Function <(1.2)*Z*). It means that I wanna impose CP optimizer to find solutions which are at most 20% more costly than the best current objective value.

    I think that I can remove the objective function and add my optimality cut during search in cp.next(). Is it right?

    The only question is how to add the new optimality cut in the loop of cp.next(). I found out that I can I can use cp.add() to add my cut during the search, but the my objective function has been calculated by IloNumExpr which does not match with the argument of cp.add(). What can I do?

     

    my code is like this:

     

     

    IloNumExpr OBJECTIVE = IloNumExpr(env,0);

    //Building the objective expression

    while(cp.next()){

           //cp.add (OBJECTIVE< (1.2)*Z*)   

    }

     

     

    Sorry for my long post and thanks in advance for your help


    #CPOptimizer
    #DecisionOptimization


  • 2.  Re: adding relaxed optimality cuts

    Posted 05/02/13 11:01 AM

    Originally posted by: Philippe_Refalo


     

    Dear Hossein, 
     
    Sorry for the late reply.
     
    It is not possible to relax constraints during CP Optimizer search so you cannot replace the constraint that forces the objective to improve by another one. Instead, I suggest to proceed in three steps:
     
    1. Call cp.next several times to improve the objective function until improvement becomes impossible or too hard. For this purpose you can change the branch limit between each call to cp.next(). This limit determines the effort that you are ready to do for improving the solution. 
     
    2. Constrain the objective function to be less than 1.2 * Z*, Z* being the best objective value obtained at step 1. 
     
    3. Perform several search runs by iterating over cp.next(). Each run can stop whenever you consider that further searching will not pay off using a limit as in step 1. Note that to create diversity during these runs you need at least to change the RandomSeed between each run, otherwise you could endup finding the same solutions, but you can also introduce different search strategies using search phases.
     
    The solutions founds are collected and can be used as columns in the master LP. 
     
    Regards, 
     
    Philippe

    #CPOptimizer
    #DecisionOptimization


Related Content