Modelling approach to OR and combinatorial problems: API bridges

[guicho271828]

There are various domain-independent solvers available. Making the bridges to these commercial optimized solvers, competition winners or state-of-the-arts will widely enhance the ability to prototype a system that can handle difficult problems via problem compilation (i.e. mapping/compiling/transforming the original problem into a form that is compatible to the solvers, then retrieve the solution).

These solvers tend to support a common input format due to industrial standardization or simply the competition rules. Thus, making a bridge should be not so difficult.

According to https://kuomarc.wordpress.com/2012/03/05/the-uncommon-lisp-approach-to-operations-research/ , this approach is a "modelling" approach. There are "programming" approaches (which means implementing these algorithm in pure lisp), but this is a different topic. For exmaple, https://jorgetavares.com/2017/05/03/gp-code-on-github/ is a "programming" approach.

• LP (P-complete) --- commercial ILOG CPLEX and Gurobi (both extremely fast & optimized)
• IP (NP-complete) --- same as LP solvers
• SAT (NP-complete) --- SAT competition winners
• MAX-SAT (NP-complete?)
• SMT (Satisfiable Modulo Theories) --- used extensively for robotics research
• Black-box optimization (GA; DE; GP; ACO; PSO; CMA-ES) --- for optimization problems w/o known gradients
• QSAT solvers (PSPACE)
• Classical planning (PSPACE)
• ASP (Answer set programming)
• CP (Constraint Programming; supports alldifferent, mutex etc.) -- MiniZinc is the common input format http://www.minizinc.org/

Progress:

• https://github.com/opsresearch/cl-opsresearch seems to contain nothing.
• SAT solver bridges : https://github.com/guicho271828/cl-sat.glucose and others

Recommended practice:

The compiler/parser for the specific format and the actual solver bridge should be decoupled.

[guicho271828]

Working in progress: https://github.com/guicho271828/cl-smt .