Examples of constraint programming¶
Examples content and source¶
The examples archive docplex-examples-master.zip contains subdirectories for the different example categories:
examples/cp/basic- This folder contains the simple examples that are a good start for learning about DOcplex.CP. Each example is self-contained and provides a textual output of the result, printed on standard output.
examples/cp/visu- This folder contains examples that provide a graphical output based on external packages numpy and matplotlib. These packages should be installed prior to running the examples. One option is to use an Anaconda Python distribution that contains all the necessary packages by default. Note that most of the examples that provide a graphical display are scheduling examples.
examples/cp/jupyter- This folder contains jupyter notebooks that mix executable code, equations, visualizations, and explanatory text. See http://jupyter.org/ for details. These notebooks can be run locally using an Anaconda Python distribution that embeds a Jupyter server.
Representative examples¶
The most representative examples that may be used as an entry point to write your own models are listed below.
Basic examples¶
This directory contains multiple examples of Python modules implementing simple problems whose solutions are provided as text on standard output.
The most representative examples in this folder are:
-
The problem involves choosing colors for the countries on a map in such a way that at most four colors (blue, white, yellow, green) are used, and no neighboring countries are the same color. In this exercise, you will find a solution for a map coloring problem with six countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands.
-
The eight queens puzzle is the problem of placing eight chess queens on an 8x8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n x n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3.
See https://en.wikipedia.org/wiki/Eight_queens_puzzle for more information.
-
In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length.
See https://en.wikipedia.org/wiki/Golomb_ruler for more information.
-
The problem is to deliver orders to several clients with a single truck. Each order consists of a given quantity of a product of a certain type (called its color). The truck must be configured in order to handle one, two, or three different colors of products. The cost for configuring the truck from a configuration A to a configuration B depends on A and B. The configuration of the truck determines its capacity and its loading cost. A truck can only be loaded with orders for the same customer. Both the cost (for configuring and loading the truck) and the number of travels needed to deliver all the orders must be minimized, the cost being the most important criterion.
Visualization / scheduling examples¶
This folder mostly contains scheduling problems. The most representative examples in this folder are:
-
In the classical Job-Shop Scheduling problem, a finite set of jobs is processed on a finite set of machines. Each job is characterized by a fixed order of operations, each of which is to be processed on a specific machine for a specified duration. Each machine can process at most one operation at a time, and, once an operation initiates processing on a given machine, it must complete processing uninterrupted. The objective of the problem is to find a schedule that minimizes the makespan of the schedule.
-
The RCPSP (Resource-Constrained Project Scheduling Problem) is a generalization of the production-specific Job-Shop (see job_shop_basic.py), Flow-Shop (see flow_shop.py), and Open-Shop (see open_shop.py) scheduling problems.
Given:
- a set of resources with given capacities,
- a network of precedence constraints between the activities, and
- for each activity and each resource the amount of the resource required by the activity over its execution,
the goal of the RCPSP is to find a schedule meeting all the constraints whose makespan (i.e., the time at which all activities are finished) is minimal.
-
This is a problem of building five houses. The masonry, roofing, painting, and so on must be scheduled. Some tasks must necessarily take place before others, and these requirements are expressed through precedence constraints.
There are two workers, and each task requires a specific worker. The worker has a calendar of days off that must be taken into account. The objective is to minimize the overall completion date.
-
This is a problem of building five houses with the following changes:
There are three workers, and each worker has a given non-negative skill level for each task. Each task requires one worker that will have to be selected among the ones who have a non-null skill level for that task. A worker can be assigned to only one task at a time. Each house has a deadline. The objective is to maximize the skill levels of the workers assigned to the tasks while respecting the deadlines.
-
This example solves a scheduling problem on two alternative heterogeneous machines. A set of tasks {a_1,…,a_n} has to be executed on either one of the two machines. Different types of tasks are distinguished, the type of task a_i is denoted tp_i.
A machine m needs a sequence dependent setup time setup(tp,tp’) to switch from a task of type tp to the next task of type tp’. Furthermore some transitions tp->tp’ are forbidden.
The two machines are different: they process tasks with different speed and have different setup times and forbidden transitions.
The objective is to minimize the makespan.
The model uses transition distances and no_overlap constraints to model machine setup times. The no_overlap constraint is specified to enforce transition distance between immediate successors on the sequence. Forbidden transitions are modeled with a very large transition distance.
-
The purpose of this example is to place a set of small squares of different sizes into a large square.
Jupyter examples¶
This folder contains several jupyter notebooks (extension .ipynb). When a notebook requires extra data, such as images, they are grouped in a sub-directory with the same name as the notebook.
The most representative examples in this folder are:
golomb_ruler.ipynb
This example solves the same problem as in the basic folder. However, it provides a lot of educational assistance for model construction, solving, and display of the solution.
house_building.ipynb
This example is similar to the one in the visu folder, but provides inline explanations on how to build and solve a scheduling model.
Running the examples¶
When the module containing a basic example is executed, the model is constructed and submitted for solving. The solution is retrieved and printed on standard output.
For instance, to run the example color.py go to the directory where you have extracted the examples directory, and enter the following command:
> python examples/cp/basic/color.py
Solving model....
Solution status: Feasible
Belgium: Yellow
Denmark: Yellow
France: Red
Germany: Green
Luxembourg: Blue
Netherlands: Red