Topic
  • 12 replies
  • Latest Post - ‏2013-05-14T05:33:53Z by DanielJunglas
Aaronlidebiao
Aaronlidebiao
10 Posts

Pinned topic How to reduce the root relaxation time for big MIQP problem?

‏2013-04-24T05:04:11Z |

Hi,

I am solving a MIQP problem for my research by CPLEX IDE 12.5.

When the binary variables are 160,000 , the engine log stop at 

"Parallel mode: deterministic, using up to 24 threads."

I think the program is doing the root relaxation. How can I speed up this process?

I can see the CPU kindof idle, only used 4% and the RAM slight increased.

Thanks.

Updated on 2013-04-26T03:23:05Z at 2013-04-26T03:23:05Z by Aaronlidebiao
  • TobiasAchterberg
    TobiasAchterberg
    8 Posts
    ACCEPTED ANSWER

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T12:52:15Z  

    Hi Tobias,

    Thanks for your reply.

    The formula you provided is useful, but what I want are' x1=1, x2=1', and then multiply by the given matrix d(1,2).

    So I think the given formula should change to 

    - x1 + z >= 0, - x2 + z >= 0, x1 + x2 - z >= 1

    I was using the indicator function in CPLEX, very similar approach to yours. In that case, the objective function is MILP. However, the new introduced variable is vary large. The CPLEX won't start to search neither.

    Regards,

    Aaron

    No, I don't think that your greater-or-equal form of the constraints makes sense. If x1 and x2 are binary, then your constraint system has only one feasible solution, namely x1 = x2 = z = 1.

    Are you allowed and willing to send your problem instance to us? If so, I could take a look and try to find some improvements in the formulation and/or the parameter settings.

  • Aaronlidebiao
    Aaronlidebiao
    10 Posts
    ACCEPTED ANSWER

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T14:31:51Z  

    No, I don't think that your greater-or-equal form of the constraints makes sense. If x1 and x2 are binary, then your constraint system has only one feasible solution, namely x1 = x2 = z = 1.

    Are you allowed and willing to send your problem instance to us? If so, I could take a look and try to find some improvements in the formulation and/or the parameter settings.

    Hi Tobias,

    Thanks for your reply.

    I agree x1=x2=z=1 is what we want.

    If I understand your formula correctly, when x1=x2=z=0, your formula still support. So I think we should use the greater equal sign.

    I posted the problem instance related question at the following thread.

    https://www.ibm.com/developerworks/community/forums/html/topic?id=b7dae9a7-6a17-4337-8108-a129b8290949#7ca35749-2366-4626-aaeb-cd5788573b65

    Regards,

    Aaron

  • DanielJunglas
    DanielJunglas
    145 Posts
    ACCEPTED ANSWER

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-14T05:33:53Z  

    Hi Daniel,

    Thanks for your reply.

    I look at the 32 jobs instance, the 99% of the time spend in the Cplex Branch and Bound. 

    But for the large instance, for example 400, the system take forever to do the root relaxation.

    Any suggestion?

    Regards,

    Debiao Li

    Did you try using the barrier algorithm for the root relaxation?

    Also you can set CPX_PARAM_MIPDISPLAY to 4 (Mathematical programming->Mixed Integer programming->General->MIP node log display information to "display nodes under MIP interval control with LP display for root node" in the OPL IDE) to get more verbose output for the solve of the root node relaxation in the engine log. Maybe this gives a hint about what is causing trouble at the root node.

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-24T05:37:44Z  

    In the settings file try to experiment with the "Mathematical Programming"->"Mixed Integer Programming"->"Strategy"->"MIP Starting Algorithm" setting.
    Do things improve if you set this to "Barrier" or "Dual Simplex"?

  • Aaronlidebiao
    Aaronlidebiao
    10 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-24T05:54:19Z  

    In the settings file try to experiment with the "Mathematical Programming"->"Mixed Integer Programming"->"Strategy"->"MIP Starting Algorithm" setting.
    Do things improve if you set this to "Barrier" or "Dual Simplex"?

    Hi Daniel,

    Thanks for your help.

    I tired the 6430 binary variable case. The original root relaxation time is 160 seconds. If I used the Dual Simplex as the starting algorithm, the time reduced to 110 seconds. The barrier is not working for my model.

    And seems like the CPLEX have a tough time to find the best integer, I don't have one best integer received after 10 mins. run. Is it nomal?

    Regards,

    Aaron

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-29T11:46:33Z  

    Yes, it can happen that CPLEX struggles to find a feasible solution. Are you sure your model does have feasible solutions? If so then you can try to set the "MIP emphasis" parameter to "find hidden feasible solutions".

  • TobiasAchterberg
    TobiasAchterberg
    8 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-30T10:26:09Z  

    If you only have binary variables in your model (or, more precisely, if in each quadratic term there is at least one binary variable), then you can reformulate your MIQP into an MILP. This sometimes helps tremendously to speed-up the solving process.

    For example, if you have a product of two binary variables x1*x2, then you can introduce an auxiliary binary variable z and add constraints:

    - x1 + z <= 0, - x2 + z <= 0, x1 + x2 - z <= 1

    Then, replace all terms "x1*x2" in your model by z.

    Tobias

    Updated on 2013-04-30T10:29:47Z at 2013-04-30T10:29:47Z by TobiasAchterberg
  • Aaronlidebiao
    Aaronlidebiao
    10 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-30T19:42:26Z  

    Yes, it can happen that CPLEX struggles to find a feasible solution. Are you sure your model does have feasible solutions? If so then you can try to set the "MIP emphasis" parameter to "find hidden feasible solutions".

    Hi Daniel,

    Thanks for you reply.

    My problem is a little complication than the Multiple travelling salesman problem. This MIP emphasis is not working.

    When I increase the job size to 400, the sever take forever to start the searching, do you have any other suggestion?

     

    Regards,

    Aaron

  • Aaronlidebiao
    Aaronlidebiao
    10 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-04-30T19:57:48Z  

    If you only have binary variables in your model (or, more precisely, if in each quadratic term there is at least one binary variable), then you can reformulate your MIQP into an MILP. This sometimes helps tremendously to speed-up the solving process.

    For example, if you have a product of two binary variables x1*x2, then you can introduce an auxiliary binary variable z and add constraints:

    - x1 + z <= 0, - x2 + z <= 0, x1 + x2 - z <= 1

    Then, replace all terms "x1*x2" in your model by z.

    Tobias

    Hi Tobias,

    Thanks for your reply.

    The formula you provided is useful, but what I want are' x1=1, x2=1', and then multiply by the given matrix d(1,2).

    So I think the given formula should change to 

    - x1 + z >= 0, - x2 + z >= 0, x1 + x2 - z >= 1

    I was using the indicator function in CPLEX, very similar approach to yours. In that case, the objective function is MILP. However, the new introduced variable is vary large. The CPLEX won't start to search neither.

    Regards,

    Aaron

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T05:13:39Z  

    Hi Daniel,

    Thanks for you reply.

    My problem is a little complication than the Multiple travelling salesman problem. This MIP emphasis is not working.

    When I increase the job size to 400, the sever take forever to start the searching, do you have any other suggestion?

     

    Regards,

    Aaron

    Did you try the profiler in the IDE? This should tell you where the time is spent. From this information it might be possible to suggest what to improve.

  • TobiasAchterberg
    TobiasAchterberg
    8 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T12:52:15Z  

    Hi Tobias,

    Thanks for your reply.

    The formula you provided is useful, but what I want are' x1=1, x2=1', and then multiply by the given matrix d(1,2).

    So I think the given formula should change to 

    - x1 + z >= 0, - x2 + z >= 0, x1 + x2 - z >= 1

    I was using the indicator function in CPLEX, very similar approach to yours. In that case, the objective function is MILP. However, the new introduced variable is vary large. The CPLEX won't start to search neither.

    Regards,

    Aaron

    No, I don't think that your greater-or-equal form of the constraints makes sense. If x1 and x2 are binary, then your constraint system has only one feasible solution, namely x1 = x2 = z = 1.

    Are you allowed and willing to send your problem instance to us? If so, I could take a look and try to find some improvements in the formulation and/or the parameter settings.

  • Aaronlidebiao
    Aaronlidebiao
    10 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T14:19:15Z  

    Did you try the profiler in the IDE? This should tell you where the time is spent. From this information it might be possible to suggest what to improve.

    Hi Daniel,

    Thanks for your reply.

    I look at the 32 jobs instance, the 99% of the time spend in the Cplex Branch and Bound. 

    But for the large instance, for example 400, the system take forever to do the root relaxation.

    Any suggestion?

    Regards,

    Debiao Li

  • Aaronlidebiao
    Aaronlidebiao
    10 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-02T14:31:51Z  

    No, I don't think that your greater-or-equal form of the constraints makes sense. If x1 and x2 are binary, then your constraint system has only one feasible solution, namely x1 = x2 = z = 1.

    Are you allowed and willing to send your problem instance to us? If so, I could take a look and try to find some improvements in the formulation and/or the parameter settings.

    Hi Tobias,

    Thanks for your reply.

    I agree x1=x2=z=1 is what we want.

    If I understand your formula correctly, when x1=x2=z=0, your formula still support. So I think we should use the greater equal sign.

    I posted the problem instance related question at the following thread.

    https://www.ibm.com/developerworks/community/forums/html/topic?id=b7dae9a7-6a17-4337-8108-a129b8290949#7ca35749-2366-4626-aaeb-cd5788573b65

    Regards,

    Aaron

  • TobiasAchterberg
    TobiasAchterberg
    8 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-08T10:11:57Z  

    Hi Tobias,

    Thanks for your reply.

    I agree x1=x2=z=1 is what we want.

    If I understand your formula correctly, when x1=x2=z=0, your formula still support. So I think we should use the greater equal sign.

    I posted the problem instance related question at the following thread.

    https://www.ibm.com/developerworks/community/forums/html/topic?id=b7dae9a7-6a17-4337-8108-a129b8290949#7ca35749-2366-4626-aaeb-cd5788573b65

    Regards,

    Aaron

    I still don't understand why you think that greater or equal makes sense here. If you do this, then the variables will automatically get fixed to 1. Thus, instead of writing the constraints with greater or equal, you can just leave away the constraints and fix the bounds of the variables to 1.

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: How to reduce the root relaxation time for big MIQP problem?

    ‏2013-05-14T05:33:53Z  

    Hi Daniel,

    Thanks for your reply.

    I look at the 32 jobs instance, the 99% of the time spend in the Cplex Branch and Bound. 

    But for the large instance, for example 400, the system take forever to do the root relaxation.

    Any suggestion?

    Regards,

    Debiao Li

    Did you try using the barrier algorithm for the root relaxation?

    Also you can set CPX_PARAM_MIPDISPLAY to 4 (Mathematical programming->Mixed Integer programming->General->MIP node log display information to "display nodes under MIP interval control with LP display for root node" in the OPL IDE) to get more verbose output for the solve of the root node relaxation in the engine log. Maybe this gives a hint about what is causing trouble at the root node.