UNB/ CS/ David Bremner/ tags/ example

This feed contains pages with tag "example".

A simple example of LP duality, from the lectures.

Posted Thu 15 Nov 2012 12:00:00 AM AST Tags: /tags/example

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

Posted Mon 01 Oct 2012 12:00:00 AM ADT Tags: /tags/example
  • 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 --interior with 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
  • This can be visualized as dot and pdf.
Posted Fri 21 Sep 2012 12:00:00 AM ADT Tags: /tags/example
Posted Thu 20 Sep 2012 12:00:00 AM ADT Tags: /tags/example
Posted Sun 16 Sep 2012 12:00:00 AM ADT Tags: /tags/example
Posted Wed 12 Sep 2012 12:00:00 AM ADT Tags: /tags/example

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.

Posted Fri 07 Sep 2012 12:00:00 AM ADT Tags: /tags/example

Here are some simple examples from the first lecture, as GMPL.

Posted Thu 06 Sep 2012 12:00:00 AM ADT Tags: /tags/example

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.

Posted Thu 25 Sep 2008 11:54:00 AM ADT Tags: /tags/example
Posted Wed 17 Sep 2008 12:00:00 AM ADT Tags: /tags/example

Here is the icecream production planner we discussed in class.

Posted Wed 10 Sep 2008 12:00:00 AM ADT Tags: /tags/example
Posted Mon 08 Sep 2008 12:00:00 AM ADT Tags: /tags/example