9
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you interested in optimal solutions, or are suboptimal solutions also acceptable? $\endgroup$ – Kevin Dalmeijer Sep 23 '19 at 3:42
  • $\begingroup$ @KevinDalmeijer, both cases are valuable. $\endgroup$ – A.Omidi Sep 23 '19 at 5:22
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Adding to the last point: Some solvers (e.g. gurobi and cplex) offer the possibility to specify some additional information on the underlying partition of the problem. This allows you to influence the fixation in the branch-and-bound procedure without having to write any additional code. Might be worth a try. (see for example gurobi.com/documentation/8.1/refman/partition.html) $\endgroup$ – JakobS Sep 24 '19 at 12:45
  • $\begingroup$ @Michael Lindahl, many thanks for your useful comment. $\endgroup$ – A.Omidi Sep 26 '19 at 20:31
  • $\begingroup$ I always find that your answers are straight to the point and very practical, thanks! I have a question: what is the difference between sequential optimization and fix-and-optimize? If I am getting it right, sequential optimization involve two levels of decisions where only the second level decisions depends on the first level decisions (the converse is false), thus there is no loss of solutions if we first take the first level decisions and then fix the associated decision variables and solve for the second level variables. It's a fix-and-optimize with no loss of solutions. Am I right? $\endgroup$ – Antarctica Jan 30 '20 at 12:08
  • 1
    $\begingroup$ Thank you very much. Both methods can lead to loss of solutions and therefore a non-optimal solution, but it off course depends on the exact model. In the sequential optimization, you can often have you most costly decisions in the first model which mean that you can have a bound on how far you are from the optimum. $\endgroup$ – Michael Lindahl Feb 2 '20 at 16:55
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ many thanks for your useful comment. $\endgroup$ – A.Omidi Sep 26 '19 at 20:31
5
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Be aware that A* is not a heuristic method, but an exact one, while simulated annealing, local search etc are heuristic methods (i.e. they may produce sub-optimal solutions). I can understand why it is confusing, since A* relies on a heuristic method to prune the search space (the better the heuristic, the better the pruning, the faster the method). In fact, the star in A* refers to the fact that it finds optimal solutions. Variants of the algorithm that are not guaranteed to find an optimal solution, are called A rather than A*. $\endgroup$ – Paul Bouman Sep 24 '19 at 14:33
  • $\begingroup$ Correct me if I'm wrong, but as far as I know A* will return a solution but not necessarily the global one (hence I would classify it as a heuristic). Getting the global solution with A* would be equivalent to enumerating all paths (to prove which path is globally optimal), which we would never do. $\endgroup$ – Nikos Kazazakis Sep 24 '19 at 18:08
  • $\begingroup$ @nikaza Please see the wiki page. More specifically, it states that using a consistent heuristic, each node is processed at most once. This would imply that not all paths need to be enumerated. $\endgroup$ – DaPurr Sep 24 '19 at 21:58
  • 2
    $\begingroup$ A* is mainly used in the context of finding paths, and it guarantees to find the (globally) shortest path, given that the heuristic is consistent (i.e. it always provides a lower bound to the destination). In fact, when you use a heuristic function that always provides 0 as a lower bound on the distance to the destination, A* is equal to Dijkstra's algorithm and it is commonly accepted that Dijkstra's algorithm is able to find a (globally optimal) shortest path (in a graph with non-negative arc weights) without the need to enumerate all paths. $\endgroup$ – Paul Bouman Sep 25 '19 at 7:11
  • $\begingroup$ many thanks for your useful comment. $\endgroup$ – A.Omidi Sep 26 '19 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.