IC SunsetThe developerWorks Connections platform will be sunset on December 31, 2019. On January 1, 2020, this forum will no longer be available. More details available on our FAQ.
Topic
  • 4 replies
  • Latest Post - ‏2015-07-20T19:14:56Z by pbhd
pbhd
pbhd
3 Posts

Pinned topic pseudo-mip much faster than continous lp

‏2015-07-17T16:56:40Z | continous cplex lp mip root-relaxation

Have an lp which is originally not a mip. When solving with simplex or network (using c++/IloCplex), it takes about 1 Minute. When adding dummy integer 0..1, then cplex treats it as mip and solves the root-relaxation within a few seconds, and because solving the mip then is trivial, the problem is solved this way very fast. This is almost always the case (Ok, sometimes its 30:60, but mip is always faster).
So my question is: How does mip parametrize the root-relaxation, so that it is so much faster? I use both for mip root-algo and the continous problem the same solver (e.g. network, or simplex), so I would assume the root-relaxation in mip and the solution of the continous case should take the same amount of time.

Or does mip use (some internal) callback of the network/simplex-solver to stop the relaxation, when the solution is "good enough"? From where does it know then what's good enough (know the theoretical best objValue)?

Because of  moments of despair, I implemented several callbacks to find out how mip parametrizes the root-relaxation, but copying these parameters and trying to use them with the network/simplex optimizer up to now had no success in terms of reaching the same solving time. On the call-stack seen in my callback, I found, that internally there is used something like CPXhybnetopt. Maybe that would do the trick? Is this routine accessible somehow in C++?

  • DanielJunglas
    DanielJunglas
    3949 Posts
    ACCEPTED ANSWER

    Re: pseudo-mip much faster than continous lp

    ‏2015-07-20T05:25:54Z  
    • pbhd
    • ‏2015-07-18T20:21:29Z

    Your guess seems to be right, out_1 as mip seems to be solved completely during preprocess, and also for out_2 the preprocessing looks different. What I want to achieve: Even when turning the problem into a pseudo-mip, there are some rare occassions when the solving takes too long. If solving a lp, I can set a time-limit and then use the solution found so far (Which is not completely perfect, but mostly). But when solving as mip and the root-relaxation times out, there seems to be no way to access the timed out imperfect root-relaxation (Once a root relaxation is found, then after a timeout mip-solutions are available)

    Well, here we go with the different run's:

    there are two lp's: out_2, which is something more real, and out_1, whose solution variables contains lots of 0. The mip-versions contain one binary variable 0..1, which is added to the obj-value.

    The listing contains of 6 runs, some of them shortened (Iteration lines removed), the different run's Header starts with ----:

    out_2 continous, algo not specified
    out_2 continous, algo network
    out_1 continuous, algo network
    out_2 mip root algo not specified
    out_2 mip root algo network
    out_1 mip root algo network

     

    In case you solve as a MIP and are terminated by a time limit, what parts of the solution do you need? If you only need the objective value that should be available from IloCplex::getObjValue().

    Would it be an option to use the callable library (C) instead of Concert (C++). The callable library provides API for this sort of advanced application: you can directly access the presolved model and solve it with whatever algorithm you like.

    Also, when solving as a MIP, you should turn off things you know are pointless, for example heuristics (CPX_PARAM_HEURFREQ).

    Finally, since there are some reductions that are applied to the MIP but not the LP, it may be possible to get those reductions applied to the LP by tweaking parameters. If you post your model file here (preferably as a sav.gz file) or send it to daniel(dot)junglas(at)de(dot)ibm(dot)com then we could take a quick look. There is no guarantee this will work but if it works it would be the most elegant thing to do.

  • DanielJunglas
    DanielJunglas
    3949 Posts

    Re: pseudo-mip much faster than continous lp

    ‏2015-07-18T10:59:54Z  

    My first guess is that MIP presolve does a better job in reducing the problem than LP presolve. Did you compare the sizes of the presolved models as they are reported in the log? Could you post a log for the LP and the MIP solve here? For the MIP solve, you should also set CPX_PARAM_MIPDISPLAY to 4 so that you can see the log of the simplex/network algorithm that is used to solve the root.

  • pbhd
    pbhd
    3 Posts

    Re: pseudo-mip much faster than continous lp

    ‏2015-07-18T20:21:29Z  

    My first guess is that MIP presolve does a better job in reducing the problem than LP presolve. Did you compare the sizes of the presolved models as they are reported in the log? Could you post a log for the LP and the MIP solve here? For the MIP solve, you should also set CPX_PARAM_MIPDISPLAY to 4 so that you can see the log of the simplex/network algorithm that is used to solve the root.

    Your guess seems to be right, out_1 as mip seems to be solved completely during preprocess, and also for out_2 the preprocessing looks different. What I want to achieve: Even when turning the problem into a pseudo-mip, there are some rare occassions when the solving takes too long. If solving a lp, I can set a time-limit and then use the solution found so far (Which is not completely perfect, but mostly). But when solving as mip and the root-relaxation times out, there seems to be no way to access the timed out imperfect root-relaxation (Once a root relaxation is found, then after a timeout mip-solutions are available)

    Well, here we go with the different run's:

    there are two lp's: out_2, which is something more real, and out_1, whose solution variables contains lots of 0. The mip-versions contain one binary variable 0..1, which is added to the obj-value.

    The listing contains of 6 runs, some of them shortened (Iteration lines removed), the different run's Header starts with ----:

    out_2 continous, algo not specified
    out_2 continous, algo network
    out_1 continuous, algo network
    out_2 mip root algo not specified
    out_2 mip root algo network
    out_1 mip root algo network

     

    Attachments

    Updated on 2015-07-18T20:31:52Z at 2015-07-18T20:31:52Z by pbhd
  • DanielJunglas
    DanielJunglas
    3949 Posts

    Re: pseudo-mip much faster than continous lp

    ‏2015-07-20T05:25:54Z  
    • pbhd
    • ‏2015-07-18T20:21:29Z

    Your guess seems to be right, out_1 as mip seems to be solved completely during preprocess, and also for out_2 the preprocessing looks different. What I want to achieve: Even when turning the problem into a pseudo-mip, there are some rare occassions when the solving takes too long. If solving a lp, I can set a time-limit and then use the solution found so far (Which is not completely perfect, but mostly). But when solving as mip and the root-relaxation times out, there seems to be no way to access the timed out imperfect root-relaxation (Once a root relaxation is found, then after a timeout mip-solutions are available)

    Well, here we go with the different run's:

    there are two lp's: out_2, which is something more real, and out_1, whose solution variables contains lots of 0. The mip-versions contain one binary variable 0..1, which is added to the obj-value.

    The listing contains of 6 runs, some of them shortened (Iteration lines removed), the different run's Header starts with ----:

    out_2 continous, algo not specified
    out_2 continous, algo network
    out_1 continuous, algo network
    out_2 mip root algo not specified
    out_2 mip root algo network
    out_1 mip root algo network

     

    In case you solve as a MIP and are terminated by a time limit, what parts of the solution do you need? If you only need the objective value that should be available from IloCplex::getObjValue().

    Would it be an option to use the callable library (C) instead of Concert (C++). The callable library provides API for this sort of advanced application: you can directly access the presolved model and solve it with whatever algorithm you like.

    Also, when solving as a MIP, you should turn off things you know are pointless, for example heuristics (CPX_PARAM_HEURFREQ).

    Finally, since there are some reductions that are applied to the MIP but not the LP, it may be possible to get those reductions applied to the LP by tweaking parameters. If you post your model file here (preferably as a sav.gz file) or send it to daniel(dot)junglas(at)de(dot)ibm(dot)com then we could take a quick look. There is no guarantee this will work but if it works it would be the most elegant thing to do.

  • pbhd
    pbhd
    3 Posts

    Re: pseudo-mip much faster than continous lp

    ‏2015-07-20T19:14:56Z  

    In case you solve as a MIP and are terminated by a time limit, what parts of the solution do you need? If you only need the objective value that should be available from IloCplex::getObjValue().

    Would it be an option to use the callable library (C) instead of Concert (C++). The callable library provides API for this sort of advanced application: you can directly access the presolved model and solve it with whatever algorithm you like.

    Also, when solving as a MIP, you should turn off things you know are pointless, for example heuristics (CPX_PARAM_HEURFREQ).

    Finally, since there are some reductions that are applied to the MIP but not the LP, it may be possible to get those reductions applied to the LP by tweaking parameters. If you post your model file here (preferably as a sav.gz file) or send it to daniel(dot)junglas(at)de(dot)ibm(dot)com then we could take a quick look. There is no guarantee this will work but if it works it would be the most elegant thing to do.

    This sounds interesting. Need the whole solution (all the variables, not only objValue), but using the C-Api could be an option, will scan thru it to find the right starting point...  Already played with the preprocess-options mentioned in the docu to let the lp-preprocess do a better job (No success yet)