tags/exampleDavid Bremnerby-nc-sa-2.5
Copyright 2020, David Bremner
https://www.cs.unb.ca/~bremner//tags/example/David Bremnerikiwiki2019-09-11T12:47:48ZExamples from Matoušek and Gärtner chapter 5https://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/chapter5/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2016-03-02T04:00:00Z
<p>Examples from chapter 5, in CPLEX lp format.</p>
<p>To read into polymake, use e.g.</p>
<pre><code> $P=lp2poly<Rational>('example-5.1.lp');
</code></pre>
<p> To solve with glpsol, use</p>
<pre><code> glpsol --lp example-5.1.lp
</code></pre>
<div class="feedlink">
</div>
First duality examplehttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/duality/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-11-15T04:00:00Z
<p>A simple example of LP duality, from the lectures.</p>
<ul>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/primal.mod">primal.mod</a> <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/primal.lp">primal.lp</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/dual.mod">dual.mod</a> <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/dual.lp">dual.lp</a></li>
</ul>
schedulinghttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/scheduling/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-10-01T03:00:00Z
<p>The ACM programming contest problem
<a href="http://uva.onlinejudge.org/external/12/1205.html">Color a tree</a> turns
out to be equivalent to scheduling with tree precedence constraints.</p>
<p>There is a fast solution to this first worked out (although not analyzed) by
<a href="http://dx.doi.org/10.1137/0123021">Horn</a> in 1972.</p>
<p>I wanted to check my solution, so I modelled this as
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/schedule.mod">an integer program</a>. Unlike Horn's algorithm,
this takes no advantage of the special tree structure of the
constraints. This is both good and bad: more general constraint DAGs
can be modelled, but it is <em>much</em> slower to solve the integer
program. Here some example data files, all trees</p>
<ul>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/schedule1.dat">schedule1.dat</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/schedule2.dat">schedule2.dat</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/schedule3.dat">schedule3.dat</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/schedule4.dat">schedule4.dat</a></li>
</ul>
bipartitehttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/bipartite/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-21T03:00:00Z
<ul>
<li>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/bipartite.mod">bipartite matching example</a> we discussed in class.</li>
<li><p>This <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/bipartite.ine">file</a> can be used to find all of the vertices (solutions).
Run with</p>
<p> lrs < bipartite.ine</p></li>
<li><p>It turns out there are only two vertices, both integer.</p></li>
</ul>
<pre>
1 1 0 0 1 1 1 0
1 0 1 1 0 1 0 1
</pre>
<p></p>
<ul>
<li>Solving with a <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/bipartite2.mod">uniform objective</a>, and
choosing <code>--interior</code> with glpsol, we get the non-integer optimal
solution</li>
</ul>
<pre>
x[1,A].val = 0.5
x[1,B].val = 0.5
x[2,A].val = 0.5
x[2,D].val = 0.5
x[3,C].val = 1.0
x[4,B].val = 0.5
x[4,D].val = 0.5
</pre>
<ul>
<li>This can be visualized as <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/bipartite2.dot">dot</a> and
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/bipartite2.pdf">pdf</a>.</li>
</ul>
largest disk in polygonhttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/polgon/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-20T03:00:00Z
<ul>
<li>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/polygon.mod">largest disk example</a> we discussed in class.</li>
</ul>
regression exampleshttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/regression/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-16T03:00:00Z
<ul>
<li><p>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/regression.mod">line fitting example</a> we discussed in class.</p></li>
<li><p>Here is the simple <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation.mod">linear separation</a>
example. The <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation2.mod">quadratic version</a> can be visualized using
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation2.rkt/">racket</a> (<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation2.pdf">pdf</a>)</p></li>
<li><p>We can also fix <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation3.mod">other parameters</a>
to obtain the model from the book, and another one.
The solutions are visualized using <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation3.rkt/">racket</a> (<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/separation3.pdf">pdf</a>)</p></li>
</ul>
Network flow exampleshttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/flow1/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-12T03:00:00Z
<ul>
<li><p>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/flow1.mod">simple flow example</a> we discussed in
class. <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/flow1.lp">LP format</a></p></li>
<li><p>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/flow2.mod">a slightly fancier example</a> from the
glpk source. The original example was a directed flow; this has
been brutally symmetrized (to make it consistent with the undirected
flows in our book) by adding reverse arcs. A
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/flow3.mod">less inefficient symmetrization</a> simply changes
the capacity constraints. There is also a
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/flow2.dot">dot drawing</a> of the network and the
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/residual2.dot">residual graph</a>.</p></li>
</ul>
AMPL book exampleshttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/ampl-book/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-07T03:00:00Z
<p>All of the examples from the
<a href="http://www.ampl.com/BOOK/download.html">AMPL Book</a> can be found on <a href="http://www.ampl.com/BOOK/EXAMPLES/EXAMPLES2/index_figs.html">ampl.com</a></p>
<p>To run these examples with glpsol, you will need a command line like</p>
<pre><code>glpsol -m prod.mod -d prod.dat
</code></pre>
<p>note that <code>solve</code> and <code>display</code> statements can be added to model file
in GMPL. There is also <code>printf</code> in GMPL for more control over
output. See Chapter 4 in the
<a href="http://www.cs.unb.ca/~bremner/docs/glpk/gmpl.pdf">GNU MathProg Reference</a>
for more information. See also <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/triangle/">triangle</a> for a simple example of using display.</p>
A first example LPhttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/triangle/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2012-09-06T03:00:00Z
<p>Here are some simple examples from the first lecture, as GMPL.</p>
<ul>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1.mod">triangle</a> <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1.lp">lp format</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1-unbounded.mod">remove one constraint</a> <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1-unbounded.lp">lp format</a></li>
<li><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1-infinite.mod">invert optimization direction</a> <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/example1-infinite.lp">lp format</a></li>
</ul>
Matching Students to Topicshttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/matching/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2008-09-25T14:54:00Z
<p>In CS3997 this year, I have decided to have "debates" instead of
presentations. This means that I need to make sure that each student
has has exactly one topic, <strong>and</strong> every topic is assigned to an even
number of students.</p>
<p>Another constraint is that I asked the students to list in order their
top 3 preferences. I wanted to maximize (within reason) "student
happiness", so I give weight 4 for their first choice, 2 for the
second, and 1 for their third.</p>
<p>Finally, the students are numbered <code>1...26</code> in the order they sent me
their preferences. I decided to enforce "first-come first-serve" in
the objective function, so the happiness of student 1 has more weight
than student 26. How much more is a bit of a subjective choice.</p>
<p>If you don't want to look at the solution yet, the students
<a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/preferences.mod">preferences</a> are available separately.
'happy[i,j]' measures how happy student i is being assigned topic j</p>
<p>Almost the real <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/topics.mod">solution</a> is available. In actuallity,
I first solved the problem for the first 18 students (so they didn't have to wait), and use the following</p>
<pre> printf { i in students, j in topics : x[i,j]=1 } "s.t. fix_%d_%d: x[%d,%d]=1;\n",i,j,i,j;
</pre>
<p>to print out some constraints, which I then cut and past into the model, and
resolved a week or so later when I had all of the data.</p>
Cutting Rolls of paperhttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/papercut/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2008-09-17T03:00:00Z
<p>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/papercut.mod">Paper roll cutting example from section 2.7</a>.</p>
Mmm, icecreamhttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/icecream/
<a href="../../whyCC/">by-nc-sa-2.5</a>
Copyright 2020, David Bremner
2019-09-11T12:47:48Z2008-09-10T03:00:00Z
<p>Here is the <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/icecream.mod">icecream production planner</a> we
discussed in class.</p>
The Diet Examplehttps://www.cs.unb.ca/~bremner//teaching/old/cs6375/examples/diet/
<a href="http://www.gnu.org/licenses/gpl.html">GPL3 or later</a>
2000-2008 Andrew Makhorin
2019-09-11T12:47:48Z2008-09-08T03:00:00Z
<ul>
<li><p>Simple version of <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/class-diet.mod">diet</a> LP <a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/class-diet.lp">lp format</a></p></li>
<li><p><a href="https://www.cs.unb.ca/~bremner//teaching/old/cs6375/files/diet.mod">expanded version</a> of the diet example taken from
the <span class="createlink">glpk</span> distribution.</p></li>
</ul>