0
$\begingroup$

This question is mainly geared toward Operations Research field.

I have a large Mixed Integer Program (MIP). I found a set of facet and valid inequalities which supposedly should make the LP relaxation tighter.

The problem I ran into is that my original MIP obtains the optimal solution in less computational time compared with MIP+ valid inequalities formulation. I did many experiments. I am speaking of large instances.

My guess is that adding these valid inequalities and facets make solving the LP more time consuming. Hence, it's defeating the purpose because MIP + valid inequalities now takes more time.

These inequalities have interesting theoretical properties and I don't want to give up due to their poor performance computationally.

I think my question is how I can get around it and make MIP + valid inequalities faster or justify them?

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I'm not sure you can (or should). Theoretical properties aside, the main purpose of valid inequalities is to tighten the LP bound so that the MIP solver both finds the optimal solution sooner (if you're lucky) and reaches provable optimality sooner (the main purpose). Some problems have inherently tight LP bounds, and those problems may not benefit from adding valid inequalities. Unless you are unsatisfied with your solution times without them, I doubt there's much to gain from using them.

If you are unsatisfied with solution times for the original model without the inequalities, and if you solver supports something like what CPLEX calls "lazy constraints", you could try adding the inequalities as lazy constraints. That might cause the solver to set the less promising ones aside at any given time and reduce the computational burden they add, while at the same time exploiting whatever tightening some of them provide. There's no guarantee that helps, though.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply. I actually have another formulation which uses Lazy constraints. It gives better results for sparse graphs in my problem. You answer is very insightful as I think I should rather focus on the lower bound (minimization problem) of my problem and assess the performance of these valid inequalities in improving the lower bounds rather than the upper bound (i.e., feasible solution). $\endgroup$ Commented May 21, 2018 at 20:46
  • $\begingroup$ Another thing that came to my mind is to shut off the cuts generated by GUROBI/CPLEX. I just want to know if these valid inequalities improve my lower bound or not. However, Gurobi will add many cuts and for that reason it will possibly make my added cuts obscure. $\endgroup$ Commented May 22, 2018 at 17:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.