Combinatorial optimization and LP\MIP
Linear/mixed integer programming (LP/MIP) is a well-known and widely used optimization method. By comparison, combinatorial optimization is less well known since it requires resources which, until recently, weren’t widely available.
That means customers often have questions about it:
- What is combinatorial optimization?
- Why can’t we solve combinatorial problems with the LP/MIP solver?
- What’s different about linear/mixed integer programming?
Let’s start by defining a combinatorial problem. In simple terms, it’s a decision problem when you must choose the best combination in the finite discrete space.
A good example – albeit a simple one – is the process you follow to select a parent to attend a child’s music lesson. You determine when each parent is available, compare your findings to the time when the lesson will take place and choose the better option.
Of course, a real combinatorial business problem would have far more parameters. To test all of them, even with the help of a supercomputer, would take centuries.
- How should you plan your company’s deliveries? An optimized plan must account for all possible delivery combinations.
- How should you schedule your company’s production? You must decide which of the possible production sequences best meets your needs.
A combinatorial problem doesn’t have linear dependencies; you can only solve it with an exhaustive search. We can solve some simple combinatorial problems with mixed integer optimization (MIP). However, the more discrete the problem, the more combinations the MIP engine must consider.
To solve problems efficiently, the combinatorial engine should «know» the problem it solves. If you need to solve a transportation problem, for example, the engine should «know» what time windows are and how optimization algorithms should treat them. This is fundamentally different from LP/MIP where you use equations as a universal language to define the problem.
Combinatorial optimization allows you to address business problems which you can’t solve with traditional LP/MIP optimization. The opportunity to find answers for these larger, more complex issues can help your business enjoy new levels of efficiency. Please contact us if you have any questions about how your company can use combinatorial optimization to solve your pressing business problems.