MIP starts
Example:facility, sensitivityA 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 theStartattribute on the variables. This is illustrated in thefacilityexample.
Thefacilityexample solves a simple facility location problem. The model contains a set of warehouses, and a set of plants that produce the products required in the warehouses. Each plant has a maximum production capacity and a fixed operating cost. Additionally, there is a cost associated with shipping products from a plant to a warehouse. The goal is to decide which plants should satisfy the demand for the product, given the associated capacities and costs.
The example uses a simple heuristic for choosing an initial solution: it closes the plant with the highest fixed cost. The associated solution may not be optimal, but it could produce a reasonable starting solution for the MIP optimization. The MIP start is passed to the MIP solver by setting theStartattribute before the optimization begins. In C, we set the start attribute to open all plants using the following code:
/* First, open all plants */ for (p = 0; p < nPlants; ++p) { error = GRBsetdblattrelement(model, "Start", opencol(p), 1.0); if (error) goto QUIT; }In C++:// First, open all plants for (p = 0; p < nPlants; ++p) { open[p].set(GRB_DoubleAttr_Start, 1.0); }In Java:// First, open all plants for (int p = 0; p < nPlants; ++p) { open[p].set(GRB.DoubleAttr.Start, 1.0); }In C#:// First, open all plants for (int p = 0; p < nPlants; ++p) { open[p].Start = 1.0; }In Python:# First open all plants for p in plants: open[p].Start = 1.0
When you run the example, the MIP solver reports that the start produced a feasible initial solution:
User MIP start produced solution with objective 210500 (0.01s) Loaded user MIP start with objective 210500This initial solution turns out to be optimal for the sample data. Although the computation difference is insignificant for this tiny example, providing a good starting solution can sometimes help for more difficult models.
Note that the MIP start in this example only specifies values for some of the variables — the variables that determine which plants to leave open and which plants to close. The Gurobi MIP solve uses whatever start information is provided to try to construct a complete solution.
