Combinatorial examples

The car sequencing problem

In this problem, a car assembly line is set up to build cars on a production line divided into cells. There are five cells that install options on the cars, requiring different times to perform the operation for each cell, defined as the number of cars they can process in a period of time. There are seven different cars, each requiring a different set of options.

The production plan specifies the quantity of each car to build. The objective of the model is to compute a sequence of cars that the cells can process while minimizing the number of empty cars to insert to respect the load of the cells.

To access this example, go to: examples/opl/models/Car.

See also The car sequencing example in the Language User’s Manual.

The configuration problem

This problem introduces the idea of using constraints to eliminate symmetries and contains some interesting modeling issues. It also illustrates structures, arrays indexed by variables, and logical connectives. The problem consists of plugging a set of electronic cards into racks with electric connectors. Each card is characterized by the power it requires, while each rack model is characterized by the maximal power it can supply, its number of connectors, and its price. Each card plugged into a rack uses a connector. The purpose of the model is to find an allocation of a given set of cards into the available racks.

To access this example, go to: examples/opl/config.

The Progressive Party problem

For a description of the problem and resolution methods, see The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared: Proceedings of the First International Conference on Principles and Practice of Constraint Programming, Lecture Notes In Computer Science; Vol. 976, pages 36-52, 1995, ISBN:3-540-60299-2.

• The examples are:

  The basic model: examples/opl/PPP. This is accessed using the default run configuration Basic Configuration.

• Another version of the model accesses an Excel spreadsheet, and is accessed using the run configuration Excel version.

The sports problem

This problem involves finding a schedule for a sports league. The league has 10 teams that play games over a season of 18 weeks. Each team has a home arena and plays each other team twice during the season, once in its home arena and once in the opposing team’s home arena. For each of these games, the team playing at its home arena is referred to as the home team; the team playing at the opponent’s arena is called the away team. There are 90 games altogether.

Each of the 18 weeks in the season has five identical slots to which games can be assigned. Each team plays once a week. For each pair of teams, these two teams are opponents twice in a season, and these two games must be scheduled in different halves of the season. Moreover, these two games must be scheduled at least six weeks apart. A team must play at home either the first week of the season or last week of the season but not both.

A break is a sequence of consecutive weeks in which a team plays its games either all at home or all away. No team can have a break of three or more weeks. The objective of this problem is to minimize the total number of breaks.

To access this example, go to: examples/opl/sports.

The steel mill problem

This problem is to build steel coils from slabs that are available in a work-in-process inventory of semi-finished products. We assume that there is no limitation to the number of slabs that we can request, but only a finite number of slab sizes are available.

The problem is to select a number of slabs to build the coil orders, and to satisfy the following constraints:

• Each coil order requires a specific process to build it from a slab. This process is encoded by a color.

• A coil order can be built from only one slab.

• Several coil order can be built from the same slab. But a slab can be used to produce at most two different ‘colors’ of coils.

• The sum of the sizes of each coil order built from a slab must no exceed the slab size.

  Note:

  This example is not supported if you are running CPLEX Optimization Studio in the Preview Edition.

To access this example, go to: examples/opl/steelmill.

See also Constraint programming: an inventory matching problem in the Language User’s Manual.

The team building problem

The HR department of a company organizes an integration day to welcome new employees.

The problem is to configure 10 teams of 6 people that respect the following rules:

• There are 30 new employees and 30 existing employees. They work in 6 different services lettered A to F.

• A team must have 3 existing employees and 3 new employees, and at most 4 people from the same service.

• Some new employees are coached by an existing employee, and an existing employee can coach only one new employee.

• A new employee who is coached must be in the team of his coach.

• Furthermore, employees of services A and B cannot be in the same team; employees of services E and F cannot be in the same team.

• Each person is represented by a number in 0-59; new employees are the even numbers, existing employees are the odd numbers.

  Service	Range
  A	0-19
  B	20-39
  C	40-44
  D	45-49
  E	50-54
  F	55-59

• In Service A: the coach/coached new employee couples are 0-1, 2-3, 4-5, 6-7, 8-9, and 10-11.

• In Service B: the coach/coached new employee couples are 20-21, 22-23, 24-25, 26-27, 28-29, and 30-31.

• In Services C, D, E, and F, the coach/coached new employee couples are 40-41, 42-43, 45-46, 47-48, 50-51, 52-53, 55-56, and 57-58.

• Person number 5 must be with either person 41 or person 51.

• Person number 15 must be with either person 40 or person 51.

• Person number 25 must be with either person 40 or person 50.

• Furthermore, person 20 is with person 24, or person 22 is with person 50.

To access this example, go to: examples/opl/teambuilding.

The time tabling problem

This model solves a school time tabling problem. Given teacher skills, room equipment and pupil course requirements, the model generates for each course a time table specifying a teacher, a start time, and a room.

Constraints are used to ensure that:

• the course ends after it starts,

• course numbering is chronological,

• a teacher is required once at any time point,

• the teacher can teach the discipline,

• a room is required once at any time point,

• the room can support the discipline,

• a class follows one course at a time,

• for given class and discipline, the teacher is always the same,

• a course starts and end the same half day,

• breaks are inserted between specified disciplines,

• the same discipline is not taught twice a day, and

• the morning disciplines end in the morning.

To reduce the number of decision variables, we use course start times as time points where the uniqueness of resources (classes, teachers, and rooms) is enforced.

The examples are:

• The basic model: examples/opl/timetabling. This is accessed using the run configuration Small data.

• Another version of the same model, accessed using the run configuration Large data.

See also The time tabling example in the Language User’s Manual.