Try our new documentation site (beta).
Diagnose and cope with infeasibility
Examples: feasopt, lp, 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.