Add overview of available techniques to solve NP-hard optimization problems.

[d-krupke]

It would probably be nice to have an overview of available techniques to solve NP-hard techniques such that one can see the place of CP-SAT in the bigger picture.

Here some notes on it to begin with:

• Mixed Integer Programming: Expressing your problem with fractional/integral variables+linear constraints/objective and handing it to a solver.
  • Rule of thumb: Good if it has a good linear relaxation (such as for network flow problems). Good if the primary task is to optimize a solution, not to find a feasible one (e.g., if it has a lot of logic involved).
  • Fair support of lazy model building (adding constraints and variables only if necessary).
  • Popular solvers: Gurobi, CBC, CPLEX...
  • Easy to use/implement.
  • Complex techniques in the background that require a lot of study to really master this technique.
• Custom Branch and Bound (without Linear Relaxation):
  • Sometimes best option if you need to do higher level branching (not just restricting a variable to some values).
  • Difficult to implement as you have to do most things on your own.
  • Example: CE-TSP
• LCG-based Constraint Programming such as CP-SAT:
  • Rule of thumb: Good if the problem has a lot of logic involved.
  • No support of lazy model building in CP-SAT. You can only extract some information from the previous iteration by hand with some chance to speed up the next iteration.
  • Easy to use/implement.
• (Cardinality-)SAT:
  • Extremely fast if your problem is essentially a boolean formula.
  • Only finds you a feasible solution, the optimization for some objective has to be done by you.
  • Many solvers allow excellent lazy model building as they maintain their state. Using Assumptions you can also do a lot of fast probing.
  • The solvers are not as intricate as MIP-solvers, but modelling a problem requires more knowledge and tricks.

Other techniques not mentioned:

• FD-based Constraint Programming:
  • Probably not the way to go. If you know of some example where they are better than, e.g., CP-SAT, please let me know.
• Quadratic Programming etc.
  • Usually not as powerful as MIP-solvers and most of the time you can get along with linear models.

[d-krupke]

Should be sufficiently addressed in the new subsection 'Limitations of CP-SAT'