This feed contains pages with tag "example".
Examples from chapter 5, in CPLEX lp format.
To read into polymake, use e.g.
$P=lp2poly<Rational>('example-5.1.lp');
To solve with glpsol, use
glpsol --lp example-5.1.lp
A simple example of LP duality, from the lectures.
The ACM programming contest problem Color a tree turns out to be equivalent to scheduling with tree precedence constraints.
There is a fast solution to this first worked out (although not analyzed) by Horn in 1972.
I wanted to check my solution, so I modelled this as an integer program. 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 much slower to solve the integer program. Here some example data files, all trees
- Here is the bipartite matching example we discussed in class.
This file can be used to find all of the vertices (solutions). Run with
lrs < bipartite.ine
It turns out there are only two vertices, both integer.
1 1 0 0 1 1 1 0
1 0 1 1 0 1 0 1
- Solving with a uniform objective, and
choosing
--interiorwith glpsol, we get the non-integer optimal solution
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
- Here is the largest disk example we discussed in class.
Here is the line fitting example we discussed in class.
Here is the simple linear separation example. The quadratic version can be visualized using racket (pdf)
We can also fix other parameters to obtain the model from the book, and another one. The solutions are visualized using racket (pdf)
Here is the simple flow example we discussed in class. LP format
Here is the a slightly fancier example 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 less inefficient symmetrization simply changes the capacity constraints. There is also a dot drawing of the network and the residual graph.
All of the examples from the AMPL Book can be found on ampl.com
To run these examples with glpsol, you will need a command line like
glpsol -m prod.mod -d prod.dat
note that solve and display statements can be added to model file
in GMPL. There is also printf in GMPL for more control over
output. See Chapter 4 in the
GNU MathProg Reference
for more information. See also triangle for a simple example of using display.
Here are some simple examples from the first lecture, as GMPL.
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, and every topic is assigned to an even number of students.
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.
Finally, the students are numbered 1...26 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.
If you don't want to look at the solution yet, the students preferences are available separately. 'happy[i,j]' measures how happy student i is being assigned topic j
Almost the real solution 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
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;
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.
Here is the icecream production planner we discussed in class.
expanded version of the diet example taken from the glpk distribution.