Topic
• 12 replies
• Latest Post - ‏2013-05-14T05:33:53Z by DanielJunglas
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
8 Posts

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

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

Hi Tobias,

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
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,

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.

Regards,

Aaron

• DanielJunglas
205 Posts

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

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

Hi Daniel,

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
205 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
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,

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
205 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
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
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,

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
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,

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
205 Posts

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

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

Hi Daniel,

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
8 Posts

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

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

Hi Tobias,

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
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,

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
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,

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.

Regards,

Aaron

• TobiasAchterberg
8 Posts

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

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

Hi Tobias,

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.

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
205 Posts

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

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

Hi Daniel,

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.