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.
What are the characteristics of a MIP start?
A MIP start may include continuous variables and discrete variables of various types, such as integer variables, binary variables, semi-continuous variables, semi-integer variables, or variables appearing in special ordered sets. For more information about each of those types, see these topics in this manual:
You may specify values for any combination of discrete and continuous variables. CPLEX decides how to construct a starting point from these variable-value pairs depending on the specified values and on the specified effort level. For more detail about effort level, see MIP starts and effort level.
Managing a MIP start with the advanced start switch
After a MIP start has been established for your model, you control its use by the test advanced start switch (AdvInd
in
Concert Technology; CPX_PARAM_ADVIND
in the Callable Library). At the default
setting of 1 (one) , the MIP start values that you specify are used. If you set
AdvInd
to the value 0 (zero), then the MIP start will not be used. If you set this
parameter to 2, CPLEX retains the current incumbent (if there is one), re-applies presolve, and
starts a new search from a new root. Setting 2 can be particularly useful for solving fixed MIP
models, where a start vector exists but no corresponding basis is available. For more about a fixed
MIP, see Working
with the fixed MIP problem.
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.
You may invoke relaxation induced neighborhood search on a starting solution. See Relaxation induced neighborhood search (RINS) heuristic in this manual for more about that topic.
Alternatively, you may invoke solution polishing to improve a solution known to CPLEX. See Solution polishing, also in this manual, for more about that way of proceeding.
Establishing starting values in a MIP start
You can establish
MIP starting values by using the method addMIPStart
in
a Concert Technology application, or by using CPXaddmipstarts
in a Callable Library application.
For use in the Interactive Optimizer, or as an alternative approach in a Concert Technology or Callable Library application, you can establish MIP starting values in a formatted file and then read the file.
To read a MIP start from a formatted file, use one of these:
the method
readMIPStart
in Concert Technologythe routine
CPXreadcopymipstarts
in the Callable Librarythe command
read
in the Interactive Optimizer
You can establish MIP starting values from a file in either MST or SOL format. MST and SOL share the same underlying XML format. MST format is documented in MST file format: MIP starts in the CPLEX File Formats Reference Manual. SOL format is documented in SOL file format: solution files also in the CPLEX File Formats Reference Manual.
Creating a file for a MIP start
At the end of a MIP optimization, when a feasible (not necessarily optimal) solution is still in memory, you can create an MST file for later use as starting values to another MIP problem.
from Concert Technology with the method
writeMIPStarts
from the Callable Library with the routine
CPXwritemipstarts
from the Interactive Optimizer with the
write
command
Make sure that the name of each variable is consistent between the original model and your target model when you use this approach.
When
you tell CPLEX to write a MIP start to a formatted file, you can also
specify a degree of detail to record there, such as only values of
discrete variables, values of all variables, and so forth. The write level for MST, SOL files is a parameter (WriteLevel
, CPX_PARAM_WRITELEVEL
),
documented in the CPLEX Parameter Reference Manual,
to manage the level of detail.
When CPLEX reads from such a file, it processes all the MIP starts. They will be processed at the next MIP optimization. Immediately after an optimization, the first MIP start is the MIP start corresponding to the incumbent solution, so if you write a file with multiple MIP starts, the first MIP start will be that corresponding to the incumbent.
Because processing a large number of MIP starts may be costly, CPLEX allows you to associate an individual effort level with each MIP start. The effort level tells CPLEX how to expend its effort in processing that MIP start. For more detail about effort level, see MIP starts and effort level.
MIP starts and effort level
You may want CPLEX to process multiple MIP starts differently, expending more effort on some than on others. Moreover, you may want to limit the effort CPLEX applies to MIP starts when it transforms each MIP start into a feasible solution, especially if there are many of them. In that context, you can specify a level of effort that CPLEX should expend for each MIP start to transform it into a feasible solution.
You specify the level of effort as an argument to the method or routine that adds a MIP start to a model or that modifies a MIP start. When CPLEX writes MIP starts to a file, such as a file in MST format, CPLEX records the level of effort the user specified for each MIP start. If you have not specified an effort level, CPLEX assigns a default effort level.
Here are the levels of effort and their effect:
Level 1: CPX_MIPSTART_CHECKFEAS CPLEX checks feasibility of the corresponding MIP start. This level requires you to provide values for all variables in the problem, both discrete and continuous. If any values are missing, CPLEX does not process this MIP start.
Level 2: CPX_MIPSTART_SOLVEFIXED CPLEX solves the fixed LP problem specified by the MIP start. This effort level requires you to provide values for all discrete variables. If values for any discrete variables are missing, CPLEX does not process the MIP start.
Level 3: CPX_MIPSTART_SOLVEMIP CPLEX solves a subMIP. You must specify the value of at least one discrete variable at this effort level.
Level 4: CPX_MIPSTART_REPAIR CPLEX attempts to repair the MIP start if it is infeasible, according to the parameter that sets the number of attempts to repair infeasible MIP start (
RepairTries
,CPX_PARAM_REPAIRTRIES
). You must specify the value of at least one discrete variable at this effort level, too.Level 5: CPX_MIPSTART_NOCHECK CPLEX does not delay processing to perform the usual checks. CPLEX checks only whether the MIP start is a complete solution; if the MIP start is not a complete solution, CPLEX rejects it. If the MIP start is a complete solution, CPLEX performs no further checks. At this level, CPLEX does not delay processing to check whether any constraints in the MIP start were designated as lazy constraints in the model, for example. If the solution defined by the MIP start is infeasible, behavior is undefined, as a consequence of this lack of checking.
You may specify a different level of effort for each MIP start, for example, differing levels of effort for the incumbent, for a MIP start corresponding to a solution in the solution pool, for a MIP start supplied by the user. By default, CPLEX expends effort at level 4 for the first MIP start and at level 1 (one) for other MIP starts. You may change that level of effort; you do so by means of an argument to the method or routine when you add a MIP start to a model or when you modify the MIP start.
MIP starts and repair tries
If the values specified in your
MIP start do not lead directly to an integer-feasible solution, CPLEX
applies a heuristic to try to repair the MIP start. The number of
times that CPLEX attempts to repair a MIP start is controlled by a
parameter, the number of attempts to repair infeasible MIP start (RepairTries
in
Concert Technology, CPX_PARAM_REPAIRTRIES
in
the Callable Library). If this process succeeds, the solution will
be treated as an integer solution of the current problem.
MIP starts and the solution pool
If you are solving a sequence of
problems, for example, by modifying and re-solving the model, CPLEX
creates a MIP start corresponding to the incumbent and to each member
of the solution pool. You may add other MIP starts which you have
computed. CPLEX then automatically processes all of these MIP starts,
unless you have turned off MIP starts by setting that parameter to
0 (zero). For documentation of the MIP start parameter (AdvInd
, CPX_PARAM_ADVIND
) see test advanced start switch in the CPLEX
Parameters Reference Manual.
MIP starts and the Interactive Optimizer
To write a particular
MIP start to a file from the Interactive Optimizer, use the write
command supplying the file name, the file
extension for MST formatted files, and the identifier of the MIP start,
like this:
write filename.mst id
The identifier of the MIP start may be its name or
its index number. In the Interactive Optimizer, MIP
starts are named by default like this: m1
, m2
, m3
, and so forth (that
is, m followed by a number). The index number of a MIP start ranges
from 1 (one) through the number of existing MIP starts for the current
problem.
To write all existing MIP starts from the current session of the Interactive Optimizer to a formatted file, use this command:
write filename.mst all
To delete a MIP start from the current session
of the Interactive Optimizer, use this command, where id
is
the name or index of the MIP start to delete:
change delete mipstart id
To delete a range of MIP starts, supply one the conventional options for a range in the Interactive Optimizer, using hyphen or wild card star, like these examples:
change delete mipstart 5-7
change delete mipstart *
MIP starts in the C++ API
Use the method IloCplex::addMIPStart
to
add a MIP start to your model. This method is not incremental. In
other words, successive calls of this method do not add more values
to an existing MIP start. Instead, successive calls of the method
override any existing MIP start. That is, each call of this method
creates a new MIP start.
Furthermore, this method works
only on one-dimensional arrays. If you want to create a MIP start
from a multidimensional array, you first must flatten the multidimensional
array by copying the variables into a one-dimensional array before
you call this method. Here is a sample, assuming a matrix of dimensions
m by n, with the starting value x[i][j]
in start[i][j]
, that you can adapt to your own application.
IloNumVarArray startVar(env);
IloNumArray startVal(env);
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
startVar.add(x[i][j]);
startVal.add(start[i][j]);
}
cplex.addMIPStart(startVar, startVal);
startVal.end();
startVar.end();
MIP starts in the Java API
Use the method IloCplex.addMIPStart
to
add a MIP start to your model. This method is not incremental. In
other words, successive calls of this method do not add more values
to an existing MIP start. Instead, successive calls of the method
override any existing MIP start. That is, each call of this method
creates a new MIP start.
Furthermore, this method works
only on one-dimensional arrays. If you want to create a MIP start
from a multidimensional array, you first must flatten the multidimensional
array by copying the variables into a one-dimensional array before
you call this method. Here is a sample, assuming a matrix of dimensions
m by n, with the starting value x[i][j]
in start[i][j]
, that you can adapt to your own application.
IloNumVar[] startVar = new IloNumVar[m * n];
double[] startVal = new double[m * n];
for (int i = 0, idx = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
startVar[idx] = x[i][j];
startVal[idx] = start[i][j];
++idx;
}
cplex.addMIPStart(startVar, startVal);
startVar = null;
startVal = null;