Linear Programming Examples
David Bremner
Creative Commons Non-Commercial Share-Alike 2.5 whyCC
Copyright 2008-2011, David Bremner
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/
David Bremner
ikiwiki
2017-01-08T00:11:07Z
Examples from Matoušek and Gärtner chapter 5
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/chapter5/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2016-03-04T01:47:42Z
2016-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>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5-pyramid.lp">example-5-pyramid.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Thu 17 Mar 2016 01:49:13 PM ADT</span>
</span>
</div>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5.1.lp">example-5.1.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Wed 02 Mar 2016 09:42:54 AM AST</span>
</span>
</div>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5.2.lp">example-5.2.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Thu 03 Mar 2016 09:47:42 PM AST</span>
</span>
</div>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5.2a.lp">example-5.2a.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Thu 03 Mar 2016 09:24:37 PM AST</span>
</span>
</div>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5.4a.lp">example-5.4a.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Thu 17 Mar 2016 04:33:58 PM ADT</span>
</span>
</div>
<div class="archivepage">
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example-5.4b.lp">example-5.4b.lp</a><br />
<span class="archivepagedate">
Posted <span class="date">Thu 03 Mar 2016 09:47:42 PM AST</span>
</span>
</div>
First duality example
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/duality/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2016-03-30T13:09:44Z
2012-11-15T04:00:00Z
<p>A simple example of LP duality, from the lectures.</p>
<ul>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/primal.mod">primal.mod</a> <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/primal.lp">primal.lp</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/dual.mod">dual.mod</a> <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/dual.lp">dual.lp</a></li>
</ul>
scheduling
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/scheduling/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2013-10-15T19:03:57Z
2012-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="http://www.cs.unb.ca/~bremner//teaching/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="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/schedule1.dat">schedule1.dat</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/schedule2.dat">schedule2.dat</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/schedule3.dat">schedule3.dat</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/schedule4.dat">schedule4.dat</a></li>
</ul>
Examples of graphs in glpsol
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/graphs/
<a href="http://www.gnu.org/licenses/gpl.html">GPL3 or later</a>
2000-2008 Andrew Makhorin
2012-09-28T00:44:09Z
2012-09-28T03:00:00Z
<p>There are several examples in the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/examples.tgz">glpsol examples collection</a></p>
<ul>
<li><p><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/graph.mod">graph.mod</a> shows the fanciest input format</p></li>
<li><p><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/color.mod">color.mod</a> is more interesting from a modelling point of view</p></li>
<li><p><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/vertex-cover.mod">vertex-cover.mod</a> uses the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/graph.pdf">graph from graph.mod</a>
for a vertex cover example.</p></li>
<li><p><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/independent-set.mod">independent-set.mod</a> uses the
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/graph.pdf">graph from graph.mod</a> for an independent-set
example. In this example the difference between the LP relaxation
and the integer optimal is not too bad, compared to the worst case.</p></li>
</ul>
bipartite
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/bipartite/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2012-09-25T17:20:57Z
2012-09-21T03:00:00Z
<ul>
<li>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/bipartite.mod">bipartite matching example</a> we discussed in class.</li>
<li><p>This <a href="http://www.cs.unb.ca/~bremner//teaching/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="http://www.cs.unb.ca/~bremner//teaching/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="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/bipartite2.dot">dot</a> and
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/bipartite2.pdf">pdf</a>.</li>
</ul>
largest disk in polygon
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/polgon/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2012-09-20T22:20:47Z
2012-09-20T03:00:00Z
<ul>
<li>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/polygon.mod">largest disk example</a> we discussed in class.</li>
</ul>
regression examples
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/regression/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2012-09-18T15:01:03Z
2012-09-16T03:00:00Z
<ul>
<li><p>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/regression.mod">line fitting example</a> we discussed in class.</p></li>
<li><p>Here is the simple <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation.mod">linear separation</a>
example. The <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation2.mod">quadratic version</a> can be visualized using
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation2.rkt/">racket</a> (<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation2.pdf">pdf</a>)</p></li>
<li><p>We can also fix <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation3.mod">other parameters</a>
to obtain the model from the book, and another one.
The solutions are visualized using <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation3.rkt/">racket</a> (<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/separation3.pdf">pdf</a>)</p></li>
</ul>
Network flow examples
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/flow1/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2017-01-08T00:11:07Z
2012-09-12T03:00:00Z
<ul>
<li><p>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/flow1.mod">simple flow example</a> we discussed in
class. <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/flow1.lp">LP format</a></p></li>
<li><p>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/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="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/flow3.mod">less inefficient symmetrization</a> simply changes
the capacity constraints. There is also a
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/flow2.dot">dot drawing</a> of the network and the
<a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/residual2.dot">residual graph</a>.</p></li>
</ul>
AMPL book examples
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/ampl-book/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2012-09-07T17:52:43Z
2012-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="http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/triangle/">triangle</a> for a simple example of using display.</p>
A first example LP
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/triangle/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2017-01-05T19:07:21Z
2012-09-06T03:00:00Z
<p>Here are some simple examples from the first lecture, as GMPL.</p>
<ul>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1.mod">triangle</a> <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1.lp">lp format</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1-unbounded.mod">remove one constraint</a> <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1-unbounded.lp">lp format</a></li>
<li><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1-infinite.mod">invert optimization direction</a> <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/example1-infinite.lp">lp format</a></li>
</ul>
Reading MPS files with glpk
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/readwrite/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2011-09-08T17:51:47Z
2009-12-13T01:11:00Z
<p>Recently I was asked how to read mps (old school linear programming
input) files. I couldn't think of a completely off the shelf way to
do, so I write a <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/readwrite.c/">simple c program</a> to use the
glpk library.</p>
<p>Of course in general you would want to do something other than print
it out again.</p>
Using GLPK from C++
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/glpk-cpp/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2011-09-08T17:51:47Z
2008-12-04T00:53:00Z
<div class="feedlink">
</div>
<div class="copypage">
<p>Recently I suggested to some students that they could use the
<a href="http://www.gnu.org/software/glpk">Gnu Linear Programming Toolkit</a> from C++. Shortly
afterwards I thought I had better verify that I had not just sent people
on a hopeless mission. To test things out, I decided to try using GLPK as
part of an <a href="http://arxiv.org/abs/0809.0915">ongoing project with Lars Schewe</a></p>
<p>The basic idea of this example is to use glpk to solve an integer
program with row generation.</p>
<p>The main hurdle (assuming you want to actually write object oriented c++) is how to make
the glpk callback work in an object oriented way. Luckily glpk provides a pointer "info" that can be passed to the solver, and which is passed back to the callback routine.
This can be used to keep track of what object is involved.</p>
<p>Here is the class header</p>
<div class="highlight-cc"><pre class="hl"><span class="hl ppc">#ifndef GLPSOL_HH</span>
<span class="hl ppc">#define GLPSOL_HH</span>
<span class="hl ppc">#include</span> <span class="hl pps">"LP.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"Vektor.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"glpk.h"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"combinat.hh"</span><span class="hl ppc"></span>
<span class="hl kwa">namespace</span> mpc <span class="hl opt">{</span>
<span class="hl kwc">class</span> GLPSol <span class="hl opt">:</span> <span class="hl kwc">public</span> LP <span class="hl opt">{</span>
<span class="hl kwc">private</span><span class="hl opt">:</span>
glp_iocp parm<span class="hl opt">;</span>
<span class="hl kwb">static</span> Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">></span> <span class="hl kwd">get_primal_sol</span><span class="hl opt">(</span>glp_prob <span class="hl opt">*</span>prob<span class="hl opt">);</span>
<span class="hl kwb">static void</span> <span class="hl kwd">callback</span><span class="hl opt">(</span>glp_tree <span class="hl opt">*</span>tree<span class="hl opt">,</span> <span class="hl kwb">void</span> <span class="hl opt">*</span>info<span class="hl opt">);</span>
<span class="hl kwb">static int</span> <span class="hl kwd">output_handler</span><span class="hl opt">(</span><span class="hl kwb">void</span> <span class="hl opt">*</span>info<span class="hl opt">,</span> <span class="hl kwb">const char</span> <span class="hl opt">*</span>s<span class="hl opt">);</span>
<span class="hl kwc">protected</span><span class="hl opt">:</span>
glp_prob <span class="hl opt">*</span>root<span class="hl opt">;</span>
<span class="hl kwc">public</span><span class="hl opt">:</span>
<span class="hl kwd">GLPSol</span><span class="hl opt">(</span><span class="hl kwb">int</span> columns<span class="hl opt">);</span>
<span class="hl opt">~</span><span class="hl kwd">GLPSol</span><span class="hl opt">() {};</span>
<span class="hl kwc">virtual</span> <span class="hl kwb">void</span> <span class="hl kwd">rowgen</span><span class="hl opt">(</span><span class="hl kwb">const</span> Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">> &</span>candidate<span class="hl opt">) {};</span>
<span class="hl kwb">bool</span> <span class="hl kwd">solve</span><span class="hl opt">();</span>
<span class="hl kwb">bool</span> <span class="hl kwd">add</span><span class="hl opt">(</span><span class="hl kwb">const</span> LinearConstraint <span class="hl opt">&</span>cnst<span class="hl opt">);</span>
<span class="hl opt">};</span>
<span class="hl opt">}</span>
<span class="hl ppc">#endif</span>
</pre></div>
<p>The class <code>LP</code> is just an abstract base class (like an interface for
java-heads) defining the <code>add</code> method. The method <code>rowgen</code> is virtual
because it is intended to be overridden by a subclass if row
generation is actually required. By default it does nothing.</p>
<p>Notice that the callback method here is static; that means it is
essentially a <code>C</code> function with a funny name. This will be the
function that glpk calls when it wants from help.</p>
<div class="highlight-cc"><pre class="hl"><span class="hl ppc">#include <assert.h></span>
<span class="hl ppc">#include</span> <span class="hl pps">"GLPSol.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"debug.hh"</span><span class="hl ppc"></span>
<span class="hl kwa">namespace</span> mpc<span class="hl opt">{</span>
<span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">GLPSol</span><span class="hl opt">(</span><span class="hl kwb">int</span> columns<span class="hl opt">) {</span>
<span class="hl slc">// redirect logging to my handler</span>
<span class="hl kwd">glp_term_hook</span><span class="hl opt">(</span>output_handler<span class="hl opt">,</span>NULL<span class="hl opt">);</span>
<span class="hl slc">// make an LP problem</span>
root<span class="hl opt">=</span><span class="hl kwd">glp_create_prob</span><span class="hl opt">();</span>
<span class="hl kwd">glp_add_cols</span><span class="hl opt">(</span>root<span class="hl opt">,</span>columns<span class="hl opt">);</span>
<span class="hl slc">// all of my variables are binary, my objective function is always the same</span>
<span class="hl slc">// your milage may vary</span>
<span class="hl kwa">for</span> <span class="hl opt">(</span><span class="hl kwb">int</span> j<span class="hl opt">=</span><span class="hl num">1</span><span class="hl opt">;</span> j<span class="hl opt"><=</span>columns<span class="hl opt">;</span> j<span class="hl opt">++){</span>
<span class="hl kwd">glp_set_obj_coef</span><span class="hl opt">(</span>root<span class="hl opt">,</span>j<span class="hl opt">,</span><span class="hl num">1.0</span><span class="hl opt">);</span>
<span class="hl kwd">glp_set_col_kind</span><span class="hl opt">(</span>root<span class="hl opt">,</span>j<span class="hl opt">,</span>GLP_BV<span class="hl opt">);</span>
<span class="hl opt">}</span>
<span class="hl kwd">glp_init_iocp</span><span class="hl opt">(&</span>parm<span class="hl opt">);</span>
<span class="hl slc">// here is the interesting bit; we pass the address of the current object</span>
<span class="hl slc">// into glpk along with the callback function</span>
parm<span class="hl opt">.</span>cb_func<span class="hl opt">=</span><span class="hl kwc">GLPSol</span><span class="hl opt">::</span>callback<span class="hl opt">;</span>
parm<span class="hl opt">.</span>cb_info<span class="hl opt">=</span><span class="hl kwa">this</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwb">int</span> <span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">output_handler</span><span class="hl opt">(</span><span class="hl kwb">void</span> <span class="hl opt">*</span>info<span class="hl opt">,</span> <span class="hl kwb">const char</span> <span class="hl opt">*</span>s<span class="hl opt">){</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">1</span><span class="hl opt">) <<</span> s<span class="hl opt">;</span>
<span class="hl kwa">return</span> <span class="hl num">1</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">></span> <span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">get_primal_sol</span><span class="hl opt">(</span>glp_prob <span class="hl opt">*</span>prob<span class="hl opt">){</span>
Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">></span> sol<span class="hl opt">;</span>
<span class="hl kwa">assert</span><span class="hl opt">(</span>prob<span class="hl opt">);</span>
<span class="hl kwa">for</span> <span class="hl opt">(</span><span class="hl kwb">int</span> i<span class="hl opt">=</span><span class="hl num">1</span><span class="hl opt">;</span> i<span class="hl opt"><=</span><span class="hl kwd">glp_get_num_cols</span><span class="hl opt">(</span>prob<span class="hl opt">);</span> i<span class="hl opt">++){</span>
sol<span class="hl opt">[</span>i<span class="hl opt">]=</span><span class="hl kwd">glp_get_col_prim</span><span class="hl opt">(</span>prob<span class="hl opt">,</span>i<span class="hl opt">);</span>
<span class="hl opt">}</span>
<span class="hl kwa">return</span> sol<span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl slc">// the callback function just figures out what object called glpk and forwards</span>
<span class="hl slc">// the call. I happen to decode the solution into a more convenient form, but </span>
<span class="hl slc">// you can do what you like</span>
<span class="hl kwb">void</span> <span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">callback</span><span class="hl opt">(</span>glp_tree <span class="hl opt">*</span>tree<span class="hl opt">,</span> <span class="hl kwb">void</span> <span class="hl opt">*</span>info<span class="hl opt">){</span>
GLPSol <span class="hl opt">*</span>obj<span class="hl opt">=(</span>GLPSol <span class="hl opt">*)</span>info<span class="hl opt">;</span>
<span class="hl kwa">assert</span><span class="hl opt">(</span>obj<span class="hl opt">);</span>
<span class="hl kwa">switch</span><span class="hl opt">(</span><span class="hl kwd">glp_ios_reason</span><span class="hl opt">(</span>tree<span class="hl opt">)){</span>
<span class="hl kwa">case</span> GLP_IROWGEN<span class="hl opt">:</span>
obj<span class="hl opt">-></span><span class="hl kwd">rowgen</span><span class="hl opt">(</span><span class="hl kwd">get_primal_sol</span><span class="hl opt">(</span><span class="hl kwd">glp_ios_get_prob</span><span class="hl opt">(</span>tree<span class="hl opt">)));</span>
<span class="hl kwa">break</span><span class="hl opt">;</span>
<span class="hl kwa">default</span><span class="hl opt">:</span>
<span class="hl kwa">break</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
<span class="hl kwb">bool</span> <span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">solve</span><span class="hl opt">(</span><span class="hl kwb">void</span><span class="hl opt">) {</span>
<span class="hl kwb">int</span> ret<span class="hl opt">=</span><span class="hl kwd">glp_simplex</span><span class="hl opt">(</span>root<span class="hl opt">,</span>NULL<span class="hl opt">);</span>
<span class="hl kwa">if</span> <span class="hl opt">(</span>ret<span class="hl opt">==</span><span class="hl num">0</span><span class="hl opt">)</span>
ret<span class="hl opt">=</span><span class="hl kwd">glp_intopt</span><span class="hl opt">(</span>root<span class="hl opt">,&</span>parm<span class="hl opt">);</span>
<span class="hl kwa">if</span> <span class="hl opt">(</span>ret<span class="hl opt">==</span><span class="hl num">0</span><span class="hl opt">)</span>
<span class="hl kwa">return</span> <span class="hl opt">(</span><span class="hl kwd">glp_mip_status</span><span class="hl opt">(</span>root<span class="hl opt">)==</span>GLP_OPT<span class="hl opt">);</span>
<span class="hl kwa">else</span>
<span class="hl kwa">return false</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwb">bool</span> <span class="hl kwc">GLPSol</span><span class="hl opt">::</span><span class="hl kwd">add</span><span class="hl opt">(</span><span class="hl kwb">const</span> LinearConstraint<span class="hl opt">&</span>cnst<span class="hl opt">){</span>
<span class="hl kwb">int</span> next_row<span class="hl opt">=</span><span class="hl kwd">glp_add_rows</span><span class="hl opt">(</span>root<span class="hl opt">,</span><span class="hl num">1</span><span class="hl opt">);</span>
<span class="hl slc">// for mysterious reasons, glpk wants to index from 1</span>
<span class="hl kwb">int</span> indices<span class="hl opt">[</span>cnst<span class="hl opt">.</span><span class="hl kwd">size</span><span class="hl opt">()+</span><span class="hl num">1</span><span class="hl opt">];</span>
<span class="hl kwb">double</span> coeff<span class="hl opt">[</span>cnst<span class="hl opt">.</span><span class="hl kwd">size</span><span class="hl opt">()+</span><span class="hl num">1</span><span class="hl opt">];</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">3</span><span class="hl opt">) <<</span> <span class="hl str">"adding "</span> <span class="hl opt"><<</span> cnst <span class="hl opt"><<</span> <span class="hl kwc">std</span><span class="hl opt">::</span>endl<span class="hl opt">;</span>
<span class="hl kwb">int</span> j<span class="hl opt">=</span><span class="hl num">1</span><span class="hl opt">;</span>
<span class="hl kwa">for</span> <span class="hl opt">(</span><span class="hl kwc">LinearConstraint</span><span class="hl opt">::</span>const_iterator p<span class="hl opt">=</span>cnst<span class="hl opt">.</span><span class="hl kwd">begin</span><span class="hl opt">();</span>
p<span class="hl opt">!=</span>cnst<span class="hl opt">.</span><span class="hl kwd">end</span><span class="hl opt">();</span> p<span class="hl opt">++){</span>
indices<span class="hl opt">[</span>j<span class="hl opt">]=</span>p<span class="hl opt">-></span>first<span class="hl opt">;</span>
coeff<span class="hl opt">[</span>j<span class="hl opt">]=(</span><span class="hl kwb">double</span><span class="hl opt">)</span>p<span class="hl opt">-></span>second<span class="hl opt">;</span>
j<span class="hl opt">++;</span>
<span class="hl opt">}</span>
<span class="hl kwb">int</span> gtype<span class="hl opt">=</span><span class="hl num">0</span><span class="hl opt">;</span>
<span class="hl kwa">switch</span><span class="hl opt">(</span>cnst<span class="hl opt">.</span><span class="hl kwd">type</span><span class="hl opt">()){</span>
<span class="hl kwa">case</span> LIN_LEQ<span class="hl opt">:</span>
gtype<span class="hl opt">=</span>GLP_UP<span class="hl opt">;</span>
<span class="hl kwa">break</span><span class="hl opt">;</span>
<span class="hl kwa">case</span> LIN_GEQ<span class="hl opt">:</span>
gtype<span class="hl opt">=</span>GLP_LO<span class="hl opt">;</span>
<span class="hl kwa">break</span><span class="hl opt">;</span>
<span class="hl kwa">default</span><span class="hl opt">:</span>
gtype<span class="hl opt">=</span>GLP_FX<span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwd">glp_set_row_bnds</span><span class="hl opt">(</span>root<span class="hl opt">,</span>next_row<span class="hl opt">,</span>gtype<span class="hl opt">,</span>
<span class="hl opt">(</span><span class="hl kwb">double</span><span class="hl opt">)</span>cnst<span class="hl opt">.</span><span class="hl kwd">rhs</span><span class="hl opt">(),(</span><span class="hl kwb">double</span><span class="hl opt">)</span>cnst<span class="hl opt">.</span><span class="hl kwd">rhs</span><span class="hl opt">());</span>
<span class="hl kwd">glp_set_mat_row</span><span class="hl opt">(</span>root<span class="hl opt">,</span>
next_row<span class="hl opt">,</span>
cnst<span class="hl opt">.</span><span class="hl kwd">size</span><span class="hl opt">(),</span>
indices<span class="hl opt">,</span>
coeff<span class="hl opt">);</span>
<span class="hl kwa">return true</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
</pre></div>
<p>All this is a big waste of effort unless we actually do some row
generation. I'm not especially proud of the crude rounding I do here,
but it shows how to do it, and it does, eventually solve problems.</p>
<div class="highlight-cc"><pre class="hl"><span class="hl ppc">#include</span> <span class="hl pps">"OMGLPSol.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"DualGraph.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"CutIterator.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"IntSet.hh"</span><span class="hl ppc"></span>
<span class="hl kwa">namespace</span> mpc<span class="hl opt">{</span>
<span class="hl kwb">void</span> <span class="hl kwc">OMGLPSol</span><span class="hl opt">::</span><span class="hl kwd">rowgen</span><span class="hl opt">(</span><span class="hl kwb">const</span> Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">>&</span>candidate<span class="hl opt">){</span>
<span class="hl kwa">if</span> <span class="hl opt">(</span>diameter<span class="hl opt"><=</span><span class="hl num">0</span><span class="hl opt">){</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">1</span><span class="hl opt">) <<</span> <span class="hl str">"no path constraints to generate"</span> <span class="hl opt"><<</span> <span class="hl kwc">std</span><span class="hl opt">::</span>endl<span class="hl opt">;</span>
<span class="hl kwa">return</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">3</span><span class="hl opt">) <<</span> <span class="hl str">"Generating paths for "</span> <span class="hl opt"><<</span> candidate <span class="hl opt"><<</span> <span class="hl kwc">std</span><span class="hl opt">::</span>endl<span class="hl opt">;</span>
<span class="hl slc">// this looks like a crude hack, which it is, but motivated by the</span>
<span class="hl slc">// following: the boundary complex is determined only by the signs</span>
<span class="hl slc">// of the bases, which we here represent as 0 for - and 1 for +</span>
Chirotope <span class="hl kwd">chi</span><span class="hl opt">(*</span><span class="hl kwa">this</span><span class="hl opt">);</span>
<span class="hl kwa">for</span> <span class="hl opt">(</span>Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">>::</span>const_iterator p<span class="hl opt">=</span>candidate<span class="hl opt">.</span><span class="hl kwd">begin</span><span class="hl opt">();</span>
p<span class="hl opt">!=</span>candidate<span class="hl opt">.</span><span class="hl kwd">end</span><span class="hl opt">();</span> p<span class="hl opt">++){</span>
<span class="hl kwa">if</span> <span class="hl opt">(</span>p<span class="hl opt">-></span>second <span class="hl opt">></span> <span class="hl num">0.5</span><span class="hl opt">) {</span>
chi<span class="hl opt">[</span>p<span class="hl opt">-></span>first<span class="hl opt">]=</span>SIGN_POS<span class="hl opt">;</span>
<span class="hl opt">}</span> <span class="hl kwa">else</span> <span class="hl opt">{</span>
chi<span class="hl opt">[</span>p<span class="hl opt">-></span>first<span class="hl opt">]=</span>SIGN_NEG<span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
BoundaryComplex <span class="hl kwd">bc</span><span class="hl opt">(</span>chi<span class="hl opt">);</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">3</span><span class="hl opt">) <<</span> chi<span class="hl opt">;</span>
DualGraph <span class="hl kwd">dg</span><span class="hl opt">(</span>bc<span class="hl opt">);</span>
CutIterator <span class="hl kwd">pathins</span><span class="hl opt">(*</span><span class="hl kwa">this</span><span class="hl opt">,</span>candidate<span class="hl opt">);</span>
<span class="hl kwb">int</span> paths_found<span class="hl opt">=</span>
dg<span class="hl opt">.</span><span class="hl kwd">all_paths</span><span class="hl opt">(</span>pathins<span class="hl opt">,</span>
<span class="hl kwc">IntSet</span><span class="hl opt">::</span><span class="hl kwd">lex_set</span><span class="hl opt">(</span><span class="hl kwd">elements</span><span class="hl opt">(),</span><span class="hl kwd">rank</span><span class="hl opt">()-</span><span class="hl num">1</span><span class="hl opt">,</span>source_facet<span class="hl opt">),</span>
<span class="hl kwc">IntSet</span><span class="hl opt">::</span><span class="hl kwd">lex_set</span><span class="hl opt">(</span><span class="hl kwd">elements</span><span class="hl opt">(),</span><span class="hl kwd">rank</span><span class="hl opt">()-</span><span class="hl num">1</span><span class="hl opt">,</span>sink_facet<span class="hl opt">),</span>
diameter<span class="hl opt">-</span><span class="hl num">1</span><span class="hl opt">);</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">1</span><span class="hl opt">) <<</span> <span class="hl str">"row generation found "</span> <span class="hl opt"><<</span> paths_found <span class="hl opt"><<</span> <span class="hl str">" realized paths</span><span class="hl esc">\n</span><span class="hl str">"</span><span class="hl opt">;</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">1</span><span class="hl opt">) <<</span> <span class="hl str">"effective cuts: "</span> <span class="hl opt"><<</span> pathins<span class="hl opt">.</span><span class="hl kwd">effective</span><span class="hl opt">() <<</span> <span class="hl kwc">std</span><span class="hl opt">::</span>endl<span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwb">void</span> <span class="hl kwc">OMGLPSol</span><span class="hl opt">::</span><span class="hl kwd">get_solution</span><span class="hl opt">(</span>Chirotope <span class="hl opt">&</span>chi<span class="hl opt">) {</span>
<span class="hl kwb">int</span> nv<span class="hl opt">=</span><span class="hl kwd">glp_get_num_cols</span><span class="hl opt">(</span>root<span class="hl opt">);</span>
<span class="hl kwa">for</span><span class="hl opt">(</span><span class="hl kwb">int</span> i<span class="hl opt">=</span><span class="hl num">1</span><span class="hl opt">;</span>i<span class="hl opt"><=</span>nv<span class="hl opt">;++</span>i<span class="hl opt">) {</span>
<span class="hl kwb">int</span> val<span class="hl opt">=</span><span class="hl kwd">glp_mip_col_val</span><span class="hl opt">(</span>root<span class="hl opt">,</span>i<span class="hl opt">);</span>
chi<span class="hl opt">[</span>i<span class="hl opt">]=(</span>val<span class="hl opt">==</span><span class="hl num">0</span> <span class="hl opt">?</span> SIGN_NEG <span class="hl opt">:</span> SIGN_POS<span class="hl opt">);</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
</pre></div>
<p>So ignore the problem specific way I generate constraints, the key
remaining piece of code is <code>CutIterator</code> which filters the generated
constraints to make sure they actually cut off the candidate
solution. This is crucial, because row generation must not add
constraints in the case that it cannot improve the solution, because
glpk assumes that if the user is generating cuts, the solver doesn't
have to.</p>
<div class="highlight-cc"><pre class="hl"><span class="hl ppc">#ifndef PATH_CONSTRAINT_ITERATOR_HH</span>
<span class="hl ppc">#define PATH_CONSTRAINT_ITERATOR_HH</span>
<span class="hl ppc">#include</span> <span class="hl pps">"PathConstraint.hh"</span><span class="hl ppc"></span>
<span class="hl ppc">#include</span> <span class="hl pps">"CNF.hh"</span><span class="hl ppc"></span>
<span class="hl kwa">namespace</span> mpc <span class="hl opt">{</span>
<span class="hl kwc">class</span> CutIterator <span class="hl opt">:</span> <span class="hl kwc">public std</span><span class="hl opt">::</span>iterator<span class="hl opt"><</span><span class="hl kwc">std</span><span class="hl opt">::</span>output_iterator_tag<span class="hl opt">,</span>
<span class="hl kwb">void</span><span class="hl opt">,</span>
<span class="hl kwb">void</span><span class="hl opt">,</span>
<span class="hl kwb">void</span><span class="hl opt">,</span>
<span class="hl kwb">void</span><span class="hl opt">>{</span>
<span class="hl kwc">private</span><span class="hl opt">:</span>
LP<span class="hl opt">&</span> _list<span class="hl opt">;</span>
Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">></span> _sol<span class="hl opt">;</span>
<span class="hl kwc">std</span><span class="hl opt">::</span><span class="hl kwb">size_t</span> _pcount<span class="hl opt">;</span>
<span class="hl kwc">std</span><span class="hl opt">::</span><span class="hl kwb">size_t</span> _ccount<span class="hl opt">;</span>
<span class="hl kwc">public</span><span class="hl opt">:</span>
<span class="hl kwd">CutIterator</span> <span class="hl opt">(</span>LP<span class="hl opt">&</span> list<span class="hl opt">,</span> <span class="hl kwb">const</span> Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">>&</span> sol<span class="hl opt">) :</span> <span class="hl kwd">_list</span><span class="hl opt">(</span>list<span class="hl opt">),</span><span class="hl kwd">_sol</span><span class="hl opt">(</span>sol<span class="hl opt">),</span> <span class="hl kwd">_pcount</span><span class="hl opt">(</span><span class="hl num">0</span><span class="hl opt">),</span> <span class="hl kwd">_ccount</span><span class="hl opt">(</span><span class="hl num">0</span><span class="hl opt">) {}</span>
CutIterator<span class="hl opt">&</span> <span class="hl kwc">operator</span><span class="hl opt">=(</span><span class="hl kwb">const</span> Path<span class="hl opt">&</span> p<span class="hl opt">) {</span>
PathConstraint <span class="hl kwd">pc</span><span class="hl opt">(</span>p<span class="hl opt">);</span>
_ccount<span class="hl opt">+=</span>pc<span class="hl opt">.</span><span class="hl kwd">appendTo</span><span class="hl opt">(</span>_list<span class="hl opt">,&</span>_sol<span class="hl opt">);</span>
_pcount<span class="hl opt">++;</span>
<span class="hl kwa">if</span> <span class="hl opt">(</span>_pcount <span class="hl opt">%</span><span class="hl num">10000</span><span class="hl opt">==</span><span class="hl num">0</span><span class="hl opt">) {</span>
<span class="hl kwd">DEBUG</span><span class="hl opt">(</span><span class="hl num">1</span><span class="hl opt">) <<</span> _pcount <span class="hl opt"><<</span> <span class="hl str">" paths generated"</span> <span class="hl opt"><<</span> <span class="hl kwc">std</span><span class="hl opt">::</span>endl<span class="hl opt">;</span>
<span class="hl opt">}</span>
<span class="hl kwa">return</span> <span class="hl opt">*</span><span class="hl kwa">this</span><span class="hl opt">;</span>
<span class="hl opt">}</span>
CutIterator<span class="hl opt">&</span> <span class="hl kwc">operator</span><span class="hl opt">*() {</span><span class="hl kwa">return</span> <span class="hl opt">*</span><span class="hl kwa">this</span><span class="hl opt">;}</span>
CutIterator<span class="hl opt">&</span> <span class="hl kwc">operator</span><span class="hl opt">++() {</span><span class="hl kwa">return</span> <span class="hl opt">*</span><span class="hl kwa">this</span><span class="hl opt">;}</span>
CutIterator<span class="hl opt">&</span> <span class="hl kwc">operator</span><span class="hl opt">++(</span><span class="hl kwb">int</span><span class="hl opt">) {</span><span class="hl kwa">return</span> <span class="hl opt">*</span><span class="hl kwa">this</span><span class="hl opt">;}</span>
<span class="hl kwb">int</span> <span class="hl kwd">effective</span><span class="hl opt">() {</span> <span class="hl kwa">return</span> _ccount<span class="hl opt">; };</span>
<span class="hl opt">};</span>
<span class="hl opt">}</span>
<span class="hl ppc">#endif</span>
</pre></div>
<p>Oh heck, another level of detail; the actual filtering actually
happens in the <code>appendTo</code> method the PathConstraint class. This is
just computing the dot product of two vectors. I would leave it as an
exercise to the readier, but remember some fuzz is neccesary to to
these kinds of comparisons with floating point numbers. Eventually,
the decision is made by the following <code>feasible</code> method of the
<code>LinearConstraint</code> class.</p>
<div class="highlight-cc"><pre class="hl"> <span class="hl kwb">bool</span> <span class="hl kwd">feasible</span><span class="hl opt">(</span><span class="hl kwb">const</span>
Vektor<span class="hl opt"><</span><span class="hl kwb">double</span><span class="hl opt">> &</span> x<span class="hl opt">){</span> <span class="hl kwb">double</span> sum<span class="hl opt">=</span><span class="hl num">0</span><span class="hl opt">;</span> <span class="hl kwa">for</span> <span class="hl opt">(</span>const_iterator
p<span class="hl opt">=</span><span class="hl kwd">begin</span><span class="hl opt">();</span>p<span class="hl opt">!=</span><span class="hl kwd">end</span><span class="hl opt">();</span> p<span class="hl opt">++){</span> sum<span class="hl opt">+=</span> p<span class="hl opt">-></span>second<span class="hl opt">*</span>x<span class="hl opt">.</span><span class="hl kwd">at</span><span class="hl opt">(</span>p<span class="hl opt">-></span>first<span class="hl opt">); }</span>
<span class="hl kwa">switch</span> <span class="hl opt">(</span><span class="hl kwd">type</span><span class="hl opt">()){</span>
<span class="hl kwa">case</span> LIN_LEQ<span class="hl opt">:</span>
<span class="hl kwa">return</span> <span class="hl opt">(</span>sum <span class="hl opt"><=</span> _rhs<span class="hl opt">+</span>epsilon<span class="hl opt">);</span>
<span class="hl kwa">case</span> LIN_GEQ<span class="hl opt">:</span>
<span class="hl kwa">return</span> <span class="hl opt">(</span>sum <span class="hl opt">>=</span> _rhs<span class="hl opt">-</span>epsilon<span class="hl opt">);</span>
<span class="hl kwa">default</span><span class="hl opt">:</span>
<span class="hl kwa">return</span> <span class="hl opt">(</span>sum <span class="hl opt"><=</span> _rhs<span class="hl opt">+</span>epsilon<span class="hl opt">) &&</span>
<span class="hl opt">(</span>sum <span class="hl opt">>=</span> _rhs<span class="hl opt">-</span>epsilon<span class="hl opt">);</span>
<span class="hl opt">}</span>
<span class="hl opt">}</span>
</pre></div>
<span class="tags">
Tags:
<a href="http://www.cs.unb.ca/~bremner//tags/cplusplus/" rel="tag">/tags/cplusplus</a>
<a href="http://www.cs.unb.ca/~bremner//tags/glpk/" rel="tag">/tags/glpk</a>
<a href="http://www.cs.unb.ca/~bremner//tags/integer_program/" rel="tag">/tags/integer program</a>
<a href="http://www.cs.unb.ca/~bremner//tags/optimization/" rel="tag">/tags/optimization</a>
<a href="http://www.cs.unb.ca/~bremner//tags/planet/" rel="tag">/tags/planet</a>
</span>
</ul>
</div>
<p></div></p>
Examples from glpsol
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/glpsol/
<a href="http://www.gnu.org/licenses/gpl.html">GPL3 or later</a>
2000-2008 Andrew Makhorin
2011-09-08T17:51:47Z
2008-10-11T23:52:00Z
<p>There are several examples distributed with <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/examples.tgz">glpsol</a></p>
Matching Students to Topics
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/matching/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2011-09-08T17:51:47Z
2008-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="http://www.cs.unb.ca/~bremner//teaching/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="http://www.cs.unb.ca/~bremner//teaching/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 paper
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/papercut/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2011-09-08T17:51:47Z
2008-09-17T03:00:00Z
<p>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/papercut.mod">Paper roll cutting example from section 2.7</a>.</p>
Mmm, icecream
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/icecream/
<a href="../../../whyCC/">by-nc-sa-2.5</a>
Copyright 2017, David Bremner
2011-09-08T17:51:47Z
2008-09-10T03:00:00Z
<p>Here is the <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/icecream.mod">icecream production planner</a> we
discussed in class.</p>
The Diet Example
http://www.cs.unb.ca/~bremner//teaching/cs6375/examples/diet/
<a href="http://www.gnu.org/licenses/gpl.html">GPL3 or later</a>
2000-2008 Andrew Makhorin
2017-01-06T09:52:49Z
2008-09-08T03:00:00Z
<ul>
<li><p>Simple version of <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/class-diet.mod">diet</a> LP <a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/class-diet.lp">lp format</a></p></li>
<li><p><a href="http://www.cs.unb.ca/~bremner//teaching/cs6375/files/diet.mod">expanded version</a> of the diet example taken from
the <span class="createlink">glpk</span> distribution.</p></li>
</ul>