Topic
  • 5 replies
  • Latest Post - ‏2015-04-15T08:58:44Z by GGR
qtbgo
qtbgo
116 Posts

Pinned topic combine CP and MIP using "with linear relaxation" opl keyword?

‏2014-01-25T00:58:32Z |

Hi, in this paper  Constraint and Integer Programming in OPL , Hentenryck proposed a model ( see figure 19) which combined CP and MIP using  "with linear relaxation" OPL keyword. I wonder if this method is still supported in OPL 12.6 ? I cannot find any related information in OPL 12.6 mannual.

Thanks in advance.

Updated on 2014-01-25T00:58:47Z at 2014-01-25T00:58:47Z by qtbgo
  • davidoff
    davidoff
    51 Posts

    Re: combine CP and MIP using "with linear relaxation" opl keyword?

    ‏2014-01-25T08:58:35Z  

    As far as I know, there is no generic relaxation mechanism of your CP model, nor hybridation (though hybridation has indeed existed in a very old time of Ilog libraries, namely "planner" that was the LP/MIP engine before the acquisition of CPLEX)

    There is the temporal relaxation IloCP::TemporalRelaxation that triggers linearization of scheduling constraints only, but the documentation of this parameter is not very detailed :

    IloCP.IntParam TemporalRelaxation : Integer control parameter. This advanced parameter can be used to control the usage of a temporal relaxation internal to the invoking IloCP engine. This parameter can take values IloCP.ParameterValues.On or IloCP.ParameterValues.Off, with IloCP.ParameterValues.On being the default, meaning the relaxation is used in the engine when needed. For some models, using the relaxation becomes inefficient, and you may deactivate the use of the temporal relaxation using value IloCP.ParameterValues.Off.

    However, you can "easily" write your own linearization of your CP model, runs it and communicate upper and lower bounds (coming respectively from any integer solution and the bestNode value of your MIP solve. This would be done "statically" since you run the MIP model first and then launch your CP model. Full hybridation between CP search and MIP could be done in API though, not directly in OPL, but this is much more advanced

    David

  • Rafael Daciuk
    Rafael Daciuk
    5 Posts

    Re: combine CP and MIP using "with linear relaxation" opl keyword?

    ‏2015-04-13T14:49:02Z  
    • davidoff
    • ‏2014-01-25T08:58:35Z

    As far as I know, there is no generic relaxation mechanism of your CP model, nor hybridation (though hybridation has indeed existed in a very old time of Ilog libraries, namely "planner" that was the LP/MIP engine before the acquisition of CPLEX)

    There is the temporal relaxation IloCP::TemporalRelaxation that triggers linearization of scheduling constraints only, but the documentation of this parameter is not very detailed :

    IloCP.IntParam TemporalRelaxation : Integer control parameter. This advanced parameter can be used to control the usage of a temporal relaxation internal to the invoking IloCP engine. This parameter can take values IloCP.ParameterValues.On or IloCP.ParameterValues.Off, with IloCP.ParameterValues.On being the default, meaning the relaxation is used in the engine when needed. For some models, using the relaxation becomes inefficient, and you may deactivate the use of the temporal relaxation using value IloCP.ParameterValues.Off.

    However, you can "easily" write your own linearization of your CP model, runs it and communicate upper and lower bounds (coming respectively from any integer solution and the bestNode value of your MIP solve. This would be done "statically" since you run the MIP model first and then launch your CP model. Full hybridation between CP search and MIP could be done in API though, not directly in OPL, but this is much more advanced

    David

    Dear David,

    I'm very interested in your suggestion of CP-MIP hybridation through the API. Do you know if there is an example of that?

    Where could I start this procedure?

    Thanks in advance,

    Rafael

  • DavidGravot
    DavidGravot
    1 Post

    Re: combine CP and MIP using "with linear relaxation" opl keyword?

    ‏2015-04-14T09:24:16Z  

    Dear David,

    I'm very interested in your suggestion of CP-MIP hybridation through the API. Do you know if there is an example of that?

    Where could I start this procedure?

    Thanks in advance,

    Rafael

    Actually, I'm not sure at all that full hybridation is still available  - e.g sharing variables from different solvers

    So, I should say my previous mail is a reminiscence of the old times. However, static hybridation such as the one where you loop between CP and MIP models passing bounds to each other is clearly in the scope of both OPL and APIs

  • Rafael Daciuk
    Rafael Daciuk
    5 Posts

    Re: combine CP and MIP using "with linear relaxation" opl keyword?

    ‏2015-04-14T17:07:43Z  

    Actually, I'm not sure at all that full hybridation is still available  - e.g sharing variables from different solvers

    So, I should say my previous mail is a reminiscence of the old times. However, static hybridation such as the one where you loop between CP and MIP models passing bounds to each other is clearly in the scope of both OPL and APIs

    Dear David,

    thank you very much for your prompt reply.

    We have tried "static" hybridation by solving a CP model and passing the results as initial solution for a MILP model, but the results were not what we expected in terms of performance. We are actually working in a modelling situation that derives from work done previously using OPL Studio v3.6.1, where we noticed that solving the hybrid model "with linear relaxation" provided great performance improvement.

    From this evaluation, we would really like to work further with a possible integration between the 2 approaches using the API, and we would be very glad if you could point in any direction as to how to best start this.

    Again, thank you very much for your help.

    Regards,

    Rafael

  • GGR
    GGR
    71 Posts

    Re: combine CP and MIP using "with linear relaxation" opl keyword?

    ‏2015-04-15T08:58:44Z  

    Hi

    This parameter is only related with scheduling problem (problem declared thanks to the interval variable language based for temporal problem).

    For full information about this please refer:

    Date: 25 Nov 2014

    Temporal linear relaxation in IBM ILOG CP Optimizer

    Hope that helps