How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

Question

Many practical optimization models (specially MIPs) are NP-Hard and solving them need much time even with the modern solvers like CPLEX or GUROBI. One of the best way (but not easy) is using decomposition techniques (at least for mathematician :) ). AFAIK, there are other ways to simplify MIPs which are done easier. Some of them are as follows.

• Reformulation of the original problem to a tighter problem which, It needs to enough knowledge about the current model. it may be a bit hard.
• Using some useful concepts such as Lazy constraints which cause solving the model be faster (E.g. sub tour elimination in TSP). Many of advanced solvers have had such capabilities.
• Using GAP control in the Branch and Bound algorithm to achieve the desired solution in a reasonable time.
• Solution pools to solve problems as soon as possible (especially in scheduling models) but, may return suboptimal solutions.

My question is:

Would you know other efficient ways (as mentioned above) to solve practical MIPs without using complicated methods?

Answer 1

In practical applications, you often need to speed up the optimization. Advanced decomposition methods add an extra layer of complexity to your code that needs to be maintained and kept bug-free. I, therefore, likes to avoid them to keep the code and model simple.

Here are some methods I like to use. Some of them have the downside that you won't necessarily find the optimal solution, but if you benchmark your different models you can get a good sense about the trade-offs between running time and solution quality.

Simplify the model

Identify which constraints or objectives that contribute the most to the high solution time. Often a small part of the model can have a huge impact. Try to see if the parts of the model really are necessary for the solutions to be useful. Talk to the end-users and see if there are other ways they could be formulated that would make it easier to solve.

Reduce the solution space

You will often have solutions that are very unlikely because they are expensive or have some bad features that makes them hard to use in practice. You can fix variables to zero that likely would result in bad solutions, or add some additional constraints to remove solutions that wouldn't be practical.

Warm starts

This is an easy one. Often you will have an existing solution that is almost feasible or just bad quality. Feed it into the solver as a start solution will usually give significant speed improvements.

Parameter tuning

MIP solvers are built to solve a large variety of different models. You can often get significant speed ups by tuning the parameters to your specific model. Both CPLEX and Gurobi have parameter tunning tools that can help you find better parameters.

Sequential optimization

If you have multiple levels of decisions. You can start by solving the most important decisions and fix those before you solve for the rest of the decisions. A good example is this article by Lach and Lübbecke (2012) where they solve a timetabling problem by first assigning the times for courses and then assign the rooms.

Fix-and-optimize

You can also use the MIP solver as part of a local search. If you have a start solution you can fix a part of the variables and solve the resulting smaller problem. You can then fix a different part of the variables and continue like this.

An example of this used to solve a timetabling problem can be seen in this paper by Lindahl et al. (2018).

---

_References

_{[1] Lach, G., Lübbecke, M. (2012). Curriculum based course timetabling: New solutions to Udine benchmark instances. Annals of Operations Research. 194:255-272.}

_{[2] Lindahl, M., Sørensen, M., Stidsen, T. R. (2018). A fix-and-optimize matheuristic for university timetabling. Journal of Heuristics. 24(4):645-665.}

Answer 2

In some cases #matheuristics can be quite effective; see e.g. the tutorial Fischetti M., Fischetti M. (2016) Matheuristics. In: Martí R., Panos P., Resende M. (eds) Handbook of Heuristics. Springer, Cham also available here

Answer 3

It depends on what we define as "solving". There are many heuristic methods that are designed to find feasible solutions to MIPs (I would also include MINLPs), such as the A* algorithm, simulated annealing, the local search algorithm, tunneling, evolutionary algorithms, etc. These methods are usually used when:

1. The problem is too large.
2. A solution is needed very quickly (e.g. pathfinding in video games or control problems).
3. There is no budget for a commercial solver.

Other techniques used in various solvers would include Benders decomposition, outer approximation, the Quessada-Grossman algorithm, extended supporting hyperplanes, domain reduction, feasibility pumps, and elimination of redundant constraints and variables.

Implementing any of these algorithms is not what I would call hard per se, however it takes deep knowledge of the math and programming to create scalable and numerically stable implementations of most of this stuff. In my opinion, the easiest class of methods to code for scale as a non-professional would be evolutionary algorithms, otherwise we come across difficulties such as factorising massive matrices or propagation of error across millions of constraints, which very few people know how to properly code.

In general, a commercial solver is invaluable when we want a solution that is likely to "make sense". A lot of the time, non-global solutions to MIPs (especially MILPs) tend to not make any sense in practice, unless we have a very small optimality gap. In these types of situations our only option tends to be using methods such as the ones you described, usually in the form of a commercial solver (the quality of implementation makes a huge difference).