The New Approach

Formulating production planning and other similar problems in terms of Mixed Integer Programming (MIP) has the advantages of simplicity of modelling and the use of powerful existing solvers for the canonical form (typically a matrix representation) of the resulting numerical instance of the model. However, a straightforward conversion of a MIP formulation into a canonical representation leads to a loss of the semantics of the problem, which is often required for effective solution even when using sophisticated cutting plane identification and clarification.

At the opposite end of the spectrum, modern heuristics and instance-specific techniques which inter-twine modelling and solution require considerably more time to model.

Local search methods like Tabu Search require problem-specific implementations involving thousands of lines of bespoke model description, whilst MIP models are typically only a few pages long. Usually experts in Constraint Programming (CP) are also able to develop very compact models quickly, but because this method is not yet part of the typical OR syllabus, textbooks and adequately trained personnel are scarce. Furthermore, being a very young discipline, CP still lacks a generally agreed form of problem representation.

The new approach presented here, a powerful integration of these methods, captures the problem semantics in a simple yet effective way, and its effectiveness has been demonstrated for various structures in a limited range of production planning problems in the two earlier ESPRIT projects. Indeed, this is arguably the only economically feasible approach.