<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Examples of constraint programming — DOcplex.CP: Constraint Programming Modeling for Python V2.0 documentation</title>
<link rel="stylesheet" href="_static/nature.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: './',
VERSION: 'V2.0',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: false
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link rel="top" title="DOcplex.CP: Constraint Programming Modeling for Python V2.0 documentation" href="index.html" />
<link rel="next" title="docplex.cp reference manual" href="refman.html" />
<link rel="prev" title="Creating a constraint programming model" href="creating_model.html" />
</head>
<body role="document">
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="refman.html" title="docplex.cp reference manual"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="creating_model.html" title="Creating a constraint programming model"
accesskey="P">previous</a> |</li>
<li class="nav-item nav-item-0"><a href="index.html">DOcplex.CP: Constraint Programming Modeling for Python V2.0 documentation</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="examples-of-constraint-programming">
<span id="samples"></span><h1>Examples of constraint programming<a class="headerlink" href="#examples-of-constraint-programming" title="Permalink to this headline">¶</a></h1>
<div class="section" id="downloading-the-examples">
<h2>Downloading the examples<a class="headerlink" href="#downloading-the-examples" title="Permalink to this headline">¶</a></h2>
<p>The examples can be downloaded from <a class="reference external" href="https://github.com/IBMDecisionOptimization/docplex-examples">GitHub</a>.</p>
</div>
<div class="section" id="examples-content-and-source">
<h2>Examples content and source<a class="headerlink" href="#examples-content-and-source" title="Permalink to this headline">¶</a></h2>
<p>The examples archive <code class="docutils literal"><span class="pre">docplex-examples-master.zip</span></code> contains subdirectories for the different example categories:</p>
<blockquote>
<div><dl class="docutils">
<dt><code class="docutils literal"><span class="pre">examples/cp/basic</span></code></dt>
<dd>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.</dd>
<dt><code class="docutils literal"><span class="pre">examples/cp/visu</span></code></dt>
<dd>This folder contains examples that provide a graphical output based on external packages <em>numpy</em> and <em>matplotlib</em>.
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.</dd>
<dt><code class="docutils literal"><span class="pre">examples/cp/jupyter</span></code></dt>
<dd>This folder contains <cite>jupyter</cite> notebooks that mix executable code, equations, visualizations, and explanatory
text. See <a class="reference external" href="http://jupyter.org/">http://jupyter.org/</a> for details.
These notebooks can be run locally using an Anaconda Python distribution that embeds a Jupyter server.</dd>
</dl>
</div></blockquote>
</div>
<div class="section" id="representative-examples">
<h2>Representative examples<a class="headerlink" href="#representative-examples" title="Permalink to this headline">¶</a></h2>
<p>The most representative examples that may be used as an entry point to write your own models are listed below.</p>
<div class="section" id="basic-examples">
<h3>Basic examples<a class="headerlink" href="#basic-examples" title="Permalink to this headline">¶</a></h3>
<p>This directory contains multiple examples of Python modules implementing simple problems whose solutions are provided as text on standard output.</p>
<p>The most representative examples in this folder are:</p>
<ul>
<li><p class="first"><a class="reference internal" href="basic.color.py.html"><em>color.py</em></a></p>
<blockquote>
<div><p>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.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="basic.n_queen.py.html"><em>n_queen.py</em></a></p>
<blockquote>
<div><p>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.</p>
<p>The eight queens puzzle is an example of the more general n-queens problem of
placing <cite>n</cite> queens on an <cite>n x n</cite> chessboard, where solutions exist for all natural
numbers <cite>n</cite> with the exception of <cite>n=2</cite> and <cite>n=3</cite>.</p>
<p>See <a class="reference external" href="https://en.wikipedia.org/wiki/Eight_queens_puzzle">https://en.wikipedia.org/wiki/Eight_queens_puzzle</a> for more information.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="basic.golomb_ruler.py.html"><em>golomb_ruler.py</em></a></p>
<blockquote>
<div><p>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.</p>
<p>See <a class="reference external" href="https://en.wikipedia.org/wiki/Golomb_ruler">https://en.wikipedia.org/wiki/Golomb_ruler</a> for more information.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="basic.truck_fleet.py.html"><em>truck_fleet.py</em></a></p>
<blockquote>
<div><p>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.</p>
</div></blockquote>
</li>
</ul>
</div>
<div class="section" id="visualization-scheduling-examples">
<h3>Visualization / scheduling examples<a class="headerlink" href="#visualization-scheduling-examples" title="Permalink to this headline">¶</a></h3>
<p>This folder mostly contains scheduling problems. The most representative examples in this folder are:</p>
<ul>
<li><p class="first"><a class="reference internal" href="visu.sched_square.py.html"><em>sched_square.py</em></a></p>
<blockquote>
<div><p>The purpose of this example is to place a set of small squares of different sizes into a large square.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="visu.sched_job_shop.py.html"><em>sched_job_shop.py</em></a></p>
<blockquote>
<div><p>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.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="visu.sched_RCPSP.py.html"><em>sched_RCPSP.py</em></a></p>
<blockquote>
<div><p>The RCPSP (Resource-Constrained Project Scheduling Problem) is a generalization of the production-specific Job-Shop (see
SchedJobShop.py), Flow-Shop (see SchedFlowShop.py), and Open-Shop (see SchedOpenShop.py) scheduling problems.
Given:</p>
<ul class="simple">
<li>a set of resources with given capacities,</li>
<li>a network of precedence constraints between the activities, and</li>
<li>for each activity and each resource the amount of the resource required by the activity over its execution,</li>
</ul>
<p>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.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="visu.sched_calendar.py.html"><em>sched_calendar.py</em></a></p>
<blockquote>
<div><p>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.</p>
<p>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.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="visu.sched_optional.py.html"><em>sched_optional.py</em></a></p>
<blockquote>
<div><p>This is a problem of building five houses with the following changes:</p>
<p>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.</p>
</div></blockquote>
</li>
<li><p class="first"><a class="reference internal" href="visu.sched_setup.py.html"><em>sched_setup.py</em></a></p>
<blockquote>
<div><p>This example solves a scheduling problem on two alternative heterogeneous machines.
A set of tasks <cite>{a_1,...,a_n}</cite> has to be executed on either one of the two machines.
Different types of tasks are distinguished, the type of task <cite>a_i</cite> is denoted <cite>tp_i</cite>.</p>
<p>A machine m needs a sequence dependent setup time <cite>setup(tp,tp’)</cite> to switch from a task of type <cite>tp</cite> to the
next task of type <cite>tp’</cite>. Furthermore some transitions <cite>tp->tp’</cite> are forbidden.</p>
<p>The two machines are different: they process tasks with different speed and have different setup times and
forbidden transitions.</p>
<p>The objective is to minimize the makespan.</p>
<p>The model uses transition distances and <cite>noOverlap</cite> constraints to model machine setup times.
The <cite>noOverlap</cite> constraint is specified to enforce transition distance between immediate successors on the
sequence. Forbidden transitions are modeled with a very large transition distance.</p>
</div></blockquote>
</li>
</ul>
</div>
<div class="section" id="jupyter-examples">
<h3>Jupyter examples<a class="headerlink" href="#jupyter-examples" title="Permalink to this headline">¶</a></h3>
<p>This folder contains several <cite>jupyter</cite> notebooks (extension <cite>.ipynb</cite>). When a notebook requires extra data,
such as images, they are grouped in a sub-directory with the same name as the notebook.
It also contains a replica of the Python utility module <cite>_utils_visu.py</cite> that is required to display scheduling results.</p>
<p>The most representative examples in this folder are:</p>
<ul>
<li><p class="first"><cite>golomb_ruler.ipynb</cite></p>
<blockquote>
<div><p>This example solves the same problem as in the <cite>basic</cite> folder. However, it provides a lot of
educational assistance for model construction, solving, and display of the solution.</p>
</div></blockquote>
</li>
<li><p class="first"><cite>house_building.ipynb</cite></p>
<blockquote>
<div><p>This example is similar to the one in the <cite>visu</cite> folder, but provides inline explanations
on how to build and solve a scheduling model.</p>
</div></blockquote>
</li>
</ul>
</div>
</div>
<div class="section" id="running-the-examples">
<h2>Running the examples<a class="headerlink" href="#running-the-examples" title="Permalink to this headline">¶</a></h2>
<p>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.</p>
<p>For instance, to run the example <a class="reference internal" href="basic.color.py.html"><em>color.py</em></a> go to the directory where you have
extracted the <em>examples</em> directory, and enter the following command:</p>
<div class="highlight-python"><div class="highlight"><pre><span></span>> python examples/cp/basic/color.py
Solving model....
Solution status: Feasible
Belgium: Yellow
Denmark: Yellow
France: Red
Germany: Green
Luxembourg: Blue
Netherlands: Red
</pre></div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">Examples of constraint programming</a><ul>
<li><a class="reference internal" href="#downloading-the-examples">Downloading the examples</a></li>
<li><a class="reference internal" href="#examples-content-and-source">Examples content and source</a></li>
<li><a class="reference internal" href="#representative-examples">Representative examples</a><ul>
<li><a class="reference internal" href="#basic-examples">Basic examples</a></li>
<li><a class="reference internal" href="#visualization-scheduling-examples">Visualization / scheduling examples</a></li>
<li><a class="reference internal" href="#jupyter-examples">Jupyter examples</a></li>
</ul>
</li>
<li><a class="reference internal" href="#running-the-examples">Running the examples</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="creating_model.html"
title="previous chapter">Creating a constraint programming model</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="refman.html"
title="next chapter"><strong>docplex.cp</strong> reference manual</a></p>
<div id="searchbox" style="display: none" role="search">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="refman.html" title="docplex.cp reference manual"
>next</a> |</li>
<li class="right" >
<a href="creating_model.html" title="Creating a constraint programming model"
>previous</a> |</li>
<li class="nav-item nav-item-0"><a href="index.html">DOcplex.CP: Constraint Programming Modeling for Python V2.0 documentation</a> »</li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2016, IBM.
</div>
</body>
</html>