Yasol software
(Ulf Lorenz, Jan. 2017)
Yasol is a search based solver for so called 'Quantified
mixed integer linear programs with minimax objective‘
(QMIP). The aim is to support optimization under uncertainty
in a new way, based upon rigorous formal models of
quantification and linear constraints.
While the solver is new in the sense that there are no other
QMIP solver at this time  Jan. 2017, most basic ingredients
of Yasol are not new at all. The heart of the search algorithm
is an arithmetic linear constraint database together with the
Alphabetaalgorithm which has been successfully used in gaming
programs like in chess programs since many years. In order to
realize fast backjumps as typically performed in SAT and
QBF solvers, we have extended the Alphabetaalgorithm as
roughly described in [7]. Yasol deals with constraint learning
on the so called primal side as known from SAT and QBF
solving, as well as with constraint learning on the so called
dual side, as is known from Mathematical Programming. The most
inspiring sources from our point of view are:

T. Achterberg: Constraint Integer Programming. Doctoral Thesis

T. Achterberg, T. Koch, A. Martin: Branching on History
Information. ZIBReport 0232, Berlin, 2002

H. Crowder, E.L. Johnson, M. Padberg: Solving LargeScale
ZeroOne Linear Programming Problems. Operations Research,
31:5, pp. 803834, 1983

G. Gamrath, T. Koch, A. Martin, M. Miltenberger,
D. Weninger: Progress in Presolving for Mixed Integer
Programming. ZIBReport 1348, Berlin, 2013

N. Sörensson, N. Een: MiniSat v1.13 – A SAT Solver with
ConflictClause Minimization.
minisat.se/downloads/MiniSat_v1.13_short.pdf

F. Lonsing, A. Biere. DepQBF: A DependencyAware QBF Solver.
JSAT 7(23), 71–76 (2010)

T. Ederer, M. Hartisch, U. Lorenz,
T. Opfer, J. Wolf. Yasol: An Open Source Solver for
Quantified Mixed Integer Programs. ACG 2017: 224233

J. Wolf: Quantified Linear Programming.
Doctoral Thesis.

L. Zhang: Searching for truth: Techniques for Satisfiability
of Boolean Formulas. Doctoral Thesis
Special thanks go to Alexander Martin for many fruitful
discussions and bringing the field of integer programming to
my interest.

Downloads
Yasol for Mac OS
Yasol for Linux
Yasol for Windows
Instances
