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

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
  • DanielJunglas
    DanielJunglas
    63 Posts
    ACCEPTED ANSWER

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

    ‏2013-04-24T05:37:44Z  in response to Aaronlidebiao

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

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

      ‏2013-04-24T05:54:19Z  in response to DanielJunglas

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

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

    ‏2013-04-29T11:46:33Z  in response to Aaronlidebiao

    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".

    • Aaronlidebiao
      Aaronlidebiao
      10 Posts
      ACCEPTED ANSWER

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

      ‏2013-04-30T19:42:26Z  in response to DanielJunglas

      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

      • DanielJunglas
        DanielJunglas
        63 Posts
        ACCEPTED ANSWER

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

        ‏2013-05-02T05:13:39Z  in response to Aaronlidebiao

        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.

        • Aaronlidebiao
          Aaronlidebiao
          10 Posts
          ACCEPTED ANSWER

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

          ‏2013-05-02T14:19:15Z  in response to DanielJunglas

          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

          • DanielJunglas
            DanielJunglas
            63 Posts
            ACCEPTED ANSWER

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

            ‏2013-05-14T05:33:53Z  in response to Aaronlidebiao

            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.

  • TobiasAchterberg
    TobiasAchterberg
    8 Posts
    ACCEPTED ANSWER

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

    ‏2013-04-30T10:26:09Z  in response to Aaronlidebiao

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

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

      ‏2013-04-30T19:57:48Z  in response to TobiasAchterberg

      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

      • TobiasAchterberg
        TobiasAchterberg
        8 Posts
        ACCEPTED ANSWER

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

        ‏2013-05-02T12:52:15Z  in response to Aaronlidebiao

        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.