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 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 Technology

  • the routine CPXreadcopymipstarts in the Callable Library

  • the 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

Tip:

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 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;