Try our new documentation site (beta).
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 helpful for the modeler to provide a
feasible solution along with the model itself. This is done through
the Start
attribute on the variables. This
is illustrated in the facility
example.
The facility
example 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 the Start
attribute before the
optimization begins. In C, we set the start attribute to open all
plants using the following code:
for (p = 0; p < nPlants; ++p) { error = GRBsetdblattrelement(model, "Start", opencol(p), 1.0); if (error) goto QUIT; }In Python:
for p in range(nPlants): open[p].start = 1.0
When you run the example, the MIP solver reports that the start produced a feasible initial solution:
Loaded 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.