###

Solve from Warm Start

Among the utility classes in the COIN-OR repository is a base class for
describing the data needed to warm start the solution process for a particular
solver or class of solvers. To support this option for SYMPHONY, we have
implemented such a warm start class for MILPs. The main content of the class
is a compact description of the search tree at the time the computation was
halted. This description contains complete information about the subproblem
corresponding to each node in the search tree, including the branching
decisions that lead to the creation of the node, the list of active variables
and constraints, and warm start information for the subproblem itself (which
is a linear program). All information is stored compactly using SYMPHONY's
native data structures, which store only the differences between a child and
its parent, rather than an explicit description of every node. This approach
reduces the tree's description to a fraction of the size it would otherwise
be. In addition to the tree itself, other relevant information regarding the
status of the computation is recorded, such as the current bounds and best
feasible solution found so far. Using the warm start class, the user can save
a warm start to disk, read one from disk, or restart the computation at any
point after modifying parameters or the problem data itself. This allows
the user to easily implement periodic checkpointing, to design dynamic
algorithms in which the parameters are modified after the gap reaches a
certain threshold, or to modify problem data during the solution process if
needed.

**Subsections**
*Ted Ralphs *

2010-03-24