Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
5 replies Latest Post - ‏2015-04-15T08:58:44Z by GGR
qtbgo
qtbgo
116 Posts
ACCEPTED ANSWER

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
    ACCEPTED ANSWER

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

    ‏2014-01-25T08:58:35Z  in response to qtbgo

    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
      ACCEPTED ANSWER

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

      ‏2015-04-13T14:49:02Z  in response to davidoff

      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
        ACCEPTED ANSWER

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

        ‏2015-04-14T09:24:16Z  in response to Rafael Daciuk

        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
          ACCEPTED ANSWER

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

          ‏2015-04-14T17:07:43Z  in response to DavidGravot

          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
    68 Posts
    ACCEPTED ANSWER

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

    ‏2015-04-15T08:58:44Z  in response to qtbgo

    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