Description of the problem

Tells you what to do and where to find the files.

What you are going to do

You will solve a configuration problem using a decomposition schema known as column generation.

You will use:

  • the CP Optimizer engine to solve the problem of generating new possible configurations, and

  • the CPLEX engine to solve the problem of selecting which is the best combination of configurations.

This configuration problem involves placing objects of different materials (glass, plastic, steel, wood, and copper) into bins of various types (red, blue, green), subject to capacity (each bin type has a maximum) and compatibility constraints. All objects must be placed into a bin and the total number of bins must be minimized.

Where to find the files

You will work with the vellino example at the following location:

<Install_dir>\opl\examples\opl\vellino

where <Install_dir> is your installation directory.

Compatibility constraints

The compatibility constraints are:

  1. Red bins cannot contain plastic or steel.

  2. Blue bins cannot contain wood or plastic.

  3. Green bins cannot contain steel or glass.

  4. Red bins contain at most one wooden component.

  5. Green bins contain at most two wooden components.

  6. Wood requires plastic.

  7. Glass excludes copper.

  8. Copper excludes plastic.

Decomposition and column generation

To solve this problem, the technique used is known as column generation. Basically, the problem is a linear set covering problem where each decision variable corresponds to a possible configuration. An auxiliary problem is to generate all the possible configurations. Constraint programming is used to solve this configuration generation problem, as most of the compatibility constraints are logical constraints for which the CP Optimizer engine offers good support.