Documentation

MIP starts

Example: facility, sensitivity

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. 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:

  /* 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 210500

This 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.