Originally posted by: basvdm

Hi,

I'm currently facing a problem in solving my LP problem.

Once I let CPLEX optimize my problem the relative MIP gap tolerance converges very slowly by +/-5% per hour or so.

In my LP problem, one of the constraints is containing a Big M. I think this constraint plays an important role in the computation time of the problem.

I read on the internet that it might be wise to translate such constraint into a indicator constraint. However, I tried to do this but I get a CPLEX error saying the constraint is invalid.

The Big M constraint is defined as follows:

200 x1 + 500 x2 + 600 x3 - M y1 <= 700

In which x1,x2,x3 and y1 are binary variables.

Can anyone help me translate this constraint into a valid indicator constraint?

Thanks in advance

200 x1 + 500 x2 + 600 x3 - M y1 <= 700

This can be translated into the following two indicator constraints:

y1 = 1 -> 200 x1 + 500 x2 + 600 x3 <= 700 + M
y1 = 0 -> 200 x1 + 500 x2 + 600 x3 <= 700

The first constraint is for when the indicator variable takes a value of one.  The second constraint is for when the indicator variable is zero or "complemented" (e.g., see the documentation for CPXXaddindconstr).

If you haven't already, you might also take a look at Best practices with indicator constraints.

Originally posted by: basvdm

Hi,

Thanks for your explanation.

Unfortunately, replacing the Big M constraint by this constraint results in an increase in computation time.

Maybe a stupid question, but does it make sense to go with a feasible solution with a relative mip.gap of 75%?

My model comes up with such a solution after a reasonable amount of time. If I wait for a smaller mip.gap(around 5% or so) this will take many hours.

Is it useful to set the max computation time to 15 minutes or so and just go with the best solution that is obtained until then? Or doesn't that make sense?

Thanks for your explanation.

Unfortunately, replacing the Big M constraint by this constraint results in an increase in computation time.

Maybe a stupid question, but does it make sense to go with a feasible solution with a relative mip.gap of 75%?

There are business cases where it is more important to get a "good" solution quickly rather than to have an optimal solution.  Only you can decide if this makes sense or not for your problem. 

My model comes up with such a solution after a reasonable amount of time. If I wait for a smaller mip.gap(around 5% or so) this will take many hours.

Is it useful to set the max computation time to 15 minutes or so and just go with the best solution that is obtained until then? Or doesn't that make sense?

Sure, this is similar to setting the gap above (yet another terminating condition) except that you don't even know if you will get a feasible solution.  You'll have to check that and then act accordingly (e.g., if there is no feasible solution yet you could continue for another 15 minutes).

It may be worth trying the tuning tool, if you haven't already, to see if there is some parameter that will help solve your problems faster.  The documentation on Emphasizing feasibility and optimality may also be helpful.

Finally, if you share your model here (ideally in SAV format) and/or the log output, there may be an expert on the forum here that can provide further guidance.