Documentation

Diagnose and cope with infeasibility

Examples: feasopt, lp, multiscenario, sensitivity, workforce1, workforce2, workforce3

When solving optimization models, there are some situations where the specified constraints cannot be satisfied. When this happens, you often need to either identify and repair the root cause of the infeasibility, or alternatively find a set of constraints to relax in order to obtain a feasible model. The workforce1, workforce2, and workforce3 illustrate these different strategies.

Starting with the simplest of the three examples, workforce1 formulates a simple workforce scheduling model and solves it. If the model is infeasible, it computes an Irreducible Inconsistent Subsystem (IIS). The user can then inspect this information to understand and hopefully address the source of the infeasibility in the model.

Example workforce2 is similar, except that if the model is infeasible, the example repeatedly identifies an IIS and removes one of the associated constraints from the model until the model becomes feasible. Note that it is sufficient to remove one constraint from the IIS to address that source of infeasibility, but that one IIS may not capture all sources of infeasibility. It is therefore necessary to repeat the process until the model is feasible.

Example workforce3 takes a different approach to addressing infeasibility. Rather than identifying and removing IIS members, it allows the constraints of the model to be relaxed. Like the feasopt example, an artificial variable is added to each constraint. The example sets the objective on the original variables to zero, and then solves a model that minimizes the total magnitude of the constraint relaxation.

The feasopt example demonstrates another approach to relaxing an infeasible model. It computes a feasibility relaxation for the infeasible model. A feasibility relaxation is a model that, when solved, minimizes the amount by which the solution violates the bounds and linear constraints of the original model. This method is invoked as follows:

In C:

  error = GRBfeasrelax(feasmodel, GRB_FEASRELAX_LINEAR, 1,
                       NULL, NULL, rhspen, &feasobj);

In C++:

  feasmodel1.feasRelax(GRB_FEASRELAX_LINEAR, true, false, true);

In C#:

  feasmodel1.FeasRelax(GRB.FEASRELAX_LINEAR, true, false, true);

In Java:

  feasmodel1.feasRelax(GRB.FEASRELAX_LINEAR, true, false, true);

In Python:

  feasmodel1.feasRelaxS(0, True, False, True)

The arguments to this method select the objective function for the relaxed model, the specific set of bounds and constraints that are allowed to be relaxed, and the penalties for relaxing specific bounds and constraints.