3.9 Tackling Infeasibility

One of the greatest bugbears of practical MP work is infeasibility. You have put together a model with some data but the LP code declares the resulting problem to be infeasible. What should you do? You know that the real problem isn't infeasible, so you have probably made a mistake in defining your formulation. Or has it been in specifying the data?

If you are lucky, the LP code will identify a small number of constraints and bounds on decision variables which together make the entire problem infeasible. There are some free-standing infeasibility analysers which go further than this and identify a chain of relationships which define the infeasibility. These tools are all valuable.

But it remains true that an ounce of prevention is worth a pound of cure. First of all the data should be validated before they reach the model so as to identify obvious gross errors. In practical applications this finds perhaps 80 - 90% of data errors before the optimization. Nonetheless, there are some inconsistencies which can slip through. And it is often the case that one only writes the data validation procedures once the model has been prototyped, so analysis of infeasibilities is required before this.

When you formulate your model you have an immense advantage over even the most sophisticated infeasibility analyser. You understand your problem. You know which constraints it makes sense to consider breaking. You can permit the model to violate such constraints in extremis by introducing extra decision variables in them known as explicit slacks, which are penalised heavily in the objective function. Thus quality constraints often carry explicit slacks while material balance constraints do not.

Some care is needed in specifying the penalty weights on the explicit slacks in the objective function so that constraints are violated in a "sensible" way when the data define an otherwise infeasible problem. Make the penalty weight directly proportional to the undesirability of violating the constraint and inversely proportional to the magnitude of a potential violation.

Another technique is to write constraints so that they retain their force even if other constraints are violated. We have seen this with the quality constraints in the single-mix blending problem. They apply irrespective of how much material is produced. This means that the model cannot overcome a quality infeasibility by failing to meet demand.

Using these techniques it is possible largely to convert infeasibility into measured and meaningful violations of constraints which provide strong clues as to where any problems lie in the data or in the formulation of the model.

previous contents next

Comments