Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Can someone explain how warm starts/ MIP starts work?
How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm?
I am interested in understanding how the entire warm start pipeline works in a MILP solver. I would appreciate links to any good reference papers talking about warm start.
For the simplex algorithms, warmstarting a solver typically means installing a near-optimal basis and using that as a starting point instead of doing a crash or slack basis as a first step. This works best if the starting basis is already primal feasible (for the primal simplex algorithm) or dual feasible (for the dual simplex) because that eliminates the need for a phase 1. In the special case of installing an optimal basis the algorithm should normally only need a single iteration to verify its optimality.
Simplex warmstarting is crucial to the performance of MILP solvers since the MILP solver does various modifications to a base problem to solve subproblems. Using warmstart speeds up solving these subproblems a lot, most common case is solving a node in the branch-and-bound tree. Tightening the bound of a basic variable means that the basis of the parent node stays dual feasible and hence typically only a few iterations are needed to solve the new node. For use cases where one wants to change the objective (e.g. feasibility pump) one can use the primal simplex with warmstart to improve performance.
Note that inside a solver and potentially in a solver API it is also possible to use what I would call hotstart. Instead of just using the basis, the simplex algorithm can also store additional information such as a factorization of this basis and steepest edge weights for pricing. This can further improve the performance when solving only slightly changed subproblems.
For MILP solvers, the warmstart input is typically a primal solution (potentially only a partial solution) that preferably is already primal feasible. Hence its objective will give a primal (upper bound in case of minimization) on the objective value and thus can be used to prune nodes.
The effectivness of "warmstarting" MILP solvers depends on a lot of factors, sometimes it is crucial, sometimes completely useless. I prefer to calling it providing an input solution or a bound, since its not the same level of effort saving as the warmstarting of a simplex algorithm. The exact way this is done depends on the solver details but you can envision it as being equivalent to the solver finding a solution really early (even before presolve) and installing it from then on as the current incumbent until a better solution is found.
When is a MILP solution worth it? An obvious factor is how good the solution provided is. Then it also matters whether it is hard to find any solutions. As a rule of thump I would say that for instances where it is hard to find any solutions or where the solutions found early by the solver are of bad quality, it makes sense to put some thought into providing a good quality input solution. For other cases, if one happens to have a solution anyways, it normally can't hurt to provide that solution to the solver.
How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm?
For proprietary closed sourced programs we have to rely on the explanation offered in the documentation. For an open source solver, such as Symphony, explanations of their methodology are offered. Questions about proprietary software can be asked about on our Reverse Engineering.SE site if you need information beyond what is available in the documentation.
Symphony uses an alternative definition duality gap to describe the distance between a solution offered from one run and a true optimal solution.
With the assistance of Saltzman and Wiecek Symphony developers created an algorithm for determining all Pareto outcomes for a bicriteria MILP by solving a sequence of related ILPs that is asymptotically optimal. In addition warm starting can be used to improve efficiency.
Bicriteria MILPs
The general form of a bicriteria (pure) ILP is \begin{array}{}\max&\{cx, dx\}\\ \text{s.t.} & Ax \le b,\\ & x \in \Bbb Z^n.\end{array}
Solutions don’t have single objective function values, but pairs of values called outcomes.
A feasible $\hat{x}$ is called efficient if there is no feasible $\bar{x}$ such that $c\bar{x}\ge c\hat{x}$ and $d\bar{x}\ge d\hat{x}$, with at least one inequality strict.
The outcome corresponding to an efficient solution is called Pareto.
The goal of a bicriteria ILP is to enumerate Pareto outcomes.
To allow resolving from a warm start, they defined a warm start class, which is derived from CoinWarmStart. The class stores a snapshot of the search tree, in a compact form by storing the node descriptions as differences from the parent.
For closed source programs the explanation of the exact algorithm isn't available publically.
CPLEX - Starting from a solution: MIP starts
Documents advanced starts; also known as warm starts or MIP starts.
When you are solving a mixed integer programming problem (MIP), you can supply hints to help CPLEX find an initial solution. These hints consist of pairs of variables and values, known as a MIP start, an advanced start, or a warm start. A MIP start might come from a different problem you have previously solved or from your knowledge of the problem, for example. You can also provide CPLEX with one or more MIP starts, that is, multiple MIP starts.
A MIP start may be a feasible solution of the model, but it need not be; it may even be infeasible or incomplete. If you are interested in debugging an infeasible MIP start, that is, if you want to discover why CPLEX regards the model inferred from the pairs of variables and values in a MIP start as infeasible, consider using the conflict refiner on that model inferred from that MIP start, as explained in Refining a conflict in a MIP start.
...
Using a MIP start
When you provide a MIP start as data, CPLEX processes it before starting branch and cut during an optimization. If one or more of the MIP starts define a solution, CPLEX installs the best of these solutions as the incumbent solution. Having an incumbent from the very beginning of branch and cut allows CPLEX to eliminate portions of the search space and thus may result in smaller branch-and-cut trees. Having an incumbent also allows CPLEX to use heuristics which require an incumbent, such as relaxation induced neighborhood search (RINS heuristic) or solution polishing.
MIP starts - Example: facility
A MIP modeler often knows how to compute a feasible solution to their problem. In cases where the MIP solver is slow in finding an initial feasible solution, it can be helpful for the modeler to provide a feasible solution along with the model itself. This is done through the Start attribute on the variables.Variable Attribute: Start, Type: double, Modifiable: Yes
The current MIP start vector. The MIP solver will attempt to build an initial solution from this vector when it is available. Note that the start can be partially populated -- the MIP solver will attempt to fill in values for missing start values. If you wish to leave the start value for a variable undefined, you can either avoid setting the Start attribute for that variable, or you can set it to a special undefined value (GRB_UNDEFINED in C and C++, or GRB.UNDEFINED in Java, .NET, and Python).Parameter Tuning Tool
The Gurobi Optimizer provides a wide variety of parameters that allow you to control the operation of the optimization engines. The level of control varies from extremely coarse-grained (e.g., the Method parameter, which allows you to choose the algorithm used to solve continuous models) to very fine-grained (e.g., the MarkowitzTol parameter, which allows you to adjust the tolerances used during simplex basis factorization). While these parameters provide a tremendous amount of user control, the immense space of possible options can present a significant challenge when you are searching for parameter settings that improve performance on a particular model. The purpose of the Gurobi tuning tool is to automate this search.
SAS/OR(R) 15.1 User's Guide: Mathematical Programming
$\color{blue}{\text{The Mixed Integer Linear Programming Solver}}$
MILP Solver Options
This section describes the options that are recognized by the MILP solver in PROC OPTMODEL. These options can be specified after a forward slash (/) in the SOLVE statement, provided that the MILP solver is explicitly specified using a WITH clause. For example, the following line could appear in PROC OPTMODEL statements:
solve with milp / allcuts=aggressive maxnodes=10000 primalin;...
Warm Start Option
PRIMALIN
enables you to input a starting solution in PROC OPTMODEL before invoking the MILP solver. Adding the PRIMALIN option to the SOLVE statement requests that the MILP solver use the current variable values as a starting solution (warm start). If the MILP solver finds that the input solution is feasible, then the input solution provides an incumbent solution and a bound for the branch-and-bound algorithm. If the solution is not feasible, the MILP solver tries to repair it. It is possible to set a variable value to the missing value '.' to mark a variable for repair. When it is difficult to find a good integer feasible solution for a problem, warm start can reduce solution time significantly.
Note: If the MILP solver produces a feasible solution, the variable values from that run can be used as the warm start solution for a subsequent run. If the warm start solution is not feasible for the subsequent run, the solver automatically tries to repair it.
