Topic
  • 1 reply
  • Latest Post - ‏2013-05-02T15:00:52Z by Philippe_Refalo
Hosssein
Hosssein
26 Posts

Pinned topic adding relaxed optimality cuts

‏2013-04-23T03:23:09Z |

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

Updated on 2013-04-23T03:51:01Z at 2013-04-23T03:51:01Z by Hosssein
  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: adding relaxed optimality cuts

    ‏2013-05-02T15:00:52Z  

     

    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