April 04, 2005
Notes on linear programming (updated 4/4)
The notes were updated to include implementation notes on page 10 on 4/4.
We have developed a set of notes on linear programming. The notes are complete, although I wouldn't be surprised if they were expanded as we cover them in class. The latest version will always be available here.
We will cover this material in class a little on Wednesday, all day Friday and Monday. The last project is to code up simplex and solve a little optimization problem.
Posted by jones at 05:23 AM | Comments (0)
April 01, 2005
More resources for learning linear programming
[a LP flash tutorial, notes on linear programming] The flash tutorial is quite nice, copmlete and slow. The notes are from Sean Warnick. They are also quite good.
Posted by jones at 03:22 PM | Comments (0)
March 30, 2005
Notes about TSP Algorithms
What to put in each node?
- Reduced matrix
- lower bound
- included edges
- excluded edges
How to generate children?
- one child for from “here” to every destination
o probably not a good idea. Queue gets too big too fast.
- Pick “here” and generate a child for the n closest cities. N children per node.
- Include or exclude an edge to generate 2 children
How to traverse the graph?
- best first search using a pruning function.
A bounding function
- the matrix reduction algorithm from Wednesday.
Way to generate initial solutions
- pick the smallest edge from A to X then smallest from X to next city (other than A) and so forth. Then return to A.
- pick a permutation of the city list and try that.
- Its probably worth doing more than 1 of these trials, but not worth doing all the permutations. You have to find the sweet spot. Well, in your improvement you can find it if that’s what you want to do.
The algorithm.
class node
members
matrix matrix, bound bound, vector solution,
Boolean optimal
etc;
methods
reduce // reduce the matrix and increase the
bound accordingly.
NextEdgeToIncludeAndExclude
// pick an edge that maximizes exclude child’s bound or some other strategy.
excludeCityEdge (i,j)
// excludes the edge from i to j, re-reduces the matrix and increases the bound as needed.
Algorithm tsp-bb (matrix M)
: (vector v, int cost, bool optimal)
priorityQueue of nodes pq;
// set up my bssf.
node bssf; // best solution so far.
(bssf.vector, bssf.bound) =
min (several different solutions);
bssf.matrix = M;
bssf.optimal = false;
// build initial node.
inode.matrix = M;
inode.bound = 0;
inode.reduce();
pq.push (inode);
while (!pq.empty) {
if (time has expired)
then bssf.optimal = false;
break;
curnode = pq.pop ();
(i,j) = curnode.NextCityEdgeToIncludeAndExclude();
node include = new node(curnode);
node exclude = new node(curnode);
exclude.excludeCityEdge (i,j);
include.includeCityEdge (i,j);
if (include.isASolution()
&& include.bound < bssf.bound)
updateBSSF (include); // set optimal = true.
pq.prune();
// the order here matters, and you can use an else
// to simplify the code.
if (include.bound < bssf.bound)
pq.push (include);
if (exclude.bound < bssf.bound)
pq.push (exclude);
}
// return the bssf.
return bssf
Class node (int,int) NextCityEdgeToIncludeAndExclude ()
// one strategy is to minimize bound on include-child.
For each (i,j) such that M[i,j] = 0
M’ = copy of array M
Set row i = infinity and column j = infinity
Set M’[j,i] = infinity
Difference = Reduce (M’) – bound
// another method…
If M[k,m] = 0 then
Difference = min (row m) + min (column k)
Excluding M[k,m].
//Just a sketch. Have fun and design your // own.
Let i,j = M[i,j] so that we get the include and exlcude bounds we want.
// make sure there are no premature cycles.
Use an array called “to” that tracks where you go “to” from city i.
Write a for-loop to see if city i is connected to itself in less than n steps where n = # of cities.
If i,j causes a premature them replace M[i,j} with infinity, reduce and try again.
Posted by jones at 11:50 AM | Comments (0)
March 25, 2005
Putting the TSP Algorithm Together
This is the algorithm so far. We will continue fleshing out the details on Monday.
What to put in each node?
- Reduced matrix
- lower bound
- included edges
- excluded edges
How to generate children?
- one child for from “here” to every destination
o probably not a good idea. Queue gets too big too fast.
- Pick “here” and generate a child for the n closest cities. N children
per node.
- Include or exclude an edge to generate 2 children
How to traverse the graph?
- best first search using a pruning function.
A bounding function
- the matrix reduction algorithm from Wednesday.
Way to generate initial solutions
- pick the smallest edge from A to X then smallest from X to next city
(other than A) and so forth. Then return to A.
- pick a permutation of the city list and try that.
- Its probably worth doing more than 1 of these trials, but not worth
doing all the permutations. You have to find the sweet spot. Well, in
your improvement you can find it if that’s what you want to do.
The algorithm.
class node
members
matrix matrix, bound bound, vector solution,
Boolean optimal
etc;
methods
reduce // reduce the matrix and increase the
bound accordingly.
NextEdgeToIncludeAndExclude
// pick an edge that maximizes exclude child’s bound or some other strategy.
excludeCityEdge (i,j)
// excludes the edge from i to j, re-reduces the matrix and increases the
bound as needed.
Algorithm tsp-bb (matrix M)
: (vector v, int cost, bool optimal)
priorityQueue of nodes pq;
// set up my bssf.
node bssf; // best solution so far.
(bssf.vector, bssf.bound) =
min (several different solutions);
bssf.matrix = M;
bssf.optimal = false;
// build initial node.
inode.matrix = M;
inode.bound = 0;
inode.reduce();
pq.push (inode);
while (!pq.empty) {
curnode = pq.pop ();
(i,j) = curnode.NextCityEdgeToIncludeAndExclude();
node include = new node(curnode);
node exclude = new node(curnode);
exclude.excludeCityEdge (i,j);
include.includeCityEdge (i,j);
if (include.isASolution()
&& include.bound < bssf.bound)
updateBSSF (include);
pq.prune();
// the order here matters, and you can use an else
// to simplify the code.
if (include.bound < bssf.bound)
pq.push (include);
if (exclude.bound < bssf.bound)
pq.push (exclude);
}
Posted by jones at 07:50 PM | Comments (0)
March 14, 2005
General form for branch and bound algorithms
Branch and bound algorithms look roughly like this. You may find this helpful for your homework and general learning.
bssf = approximate some solutions and pick the best one
push initial node onto pQueue
while (pQueue is not empty)
node = pQueue.pop()
for child = all feasible children of node.children
child.bound = compute bound on this node.
if (child.isASolution and child is better than bssf)
prune the tail of pQueue to eliminate newly non-promising nodes
if (child.bound is potentially better than bssf)
pQueue.push (child)
return bssf
Notes: be careful about what it means for a solution to be "better" than the bssf and what it means for a child to be "potentially better" than the bssf.
Posted by jones at 03:36 PM | Comments (0)
February 28, 2005
Matrix multiplication and top-down dynamic programming
Index of /~jones/cs312 see 16-matrixmemory.pdf. The notes about Floyd's algorithm are near the end.
Posted by jones at 03:10 PM | Comments (0)
February 22, 2005
Notes for introduction to dynamic programming
see Index of /~jones/cs312 and get the file 18-2005-intro-to-dp.pdf
Posted by jones at 03:20 PM | Comments (0)
February 10, 2005
Approximate schedule for recurrence relations
There's a handout (click on title to see the full post along with the link to the notes) on recurrence relations that I'll pass out in class on Friday. The schedule said it should be passed out on wednesady, but we are about 1 day behind. Updated 2/14 to include another section for today's class and more homework that will due 2/16.
Posted by jones at 07:11 PM | Comments (0)
January 25, 2005
Minimum spanning tree notes and reading
We didn't exactly get through all of Monday's lecture, however, we did have a productive discussion of minimum spanning trees. At the end of class, I said read section 3.6 (I think) that's wrong you want to read section 6.3 for the homework. The lecture notes are in this directory... [Index of /~jones/cs312/lectures/prior_semesters] On wednesday we are going to move on to Dijkstra's algorithm for shortest paths.
Posted by jones at 08:57 AM | Comments (0)
January 19, 2005
Notes for amortized analysis and Crossing the Dessert
The notes I used for the lectures on 1/19 and 1/14 in which the topics were amortized analysis and crossing the desert can be found in 0-04-amortizedpnp.pdf and 0-05-breatherdesert.pdf at this location Index of /~jones/cs312/lectures
Posted by jones at 07:51 AM | Comments (0)
January 10, 2005
Finishing big-O, and notation in lectures
The lecture on the max rule proof on Friday got a little dense. I think it would have been better if we'd discussed the idea behind the proof before diving into the detail. We might also need to discuss big-O a little more too. Very few lectures in 312 will have that much notation!
By the way, the reading for each day and the lecture notes will help you understand the lectures better. The big-O stuff comes out of these lecture notes: 011-asymptoticbounds.pdf and 012-asymptotic2.pdf in the old lecture notes directory.
Posted by jones at 02:27 PM | Comments (0)
January 04, 2005
Notes from Last Year
[Lecture notes] They are mostly pdf files, with some text files. The first two digits of the file name are roughly the order in which the lectures were given. We will probably not do very many powerpoint lectures (since there's only 10 students in the class, we can just discuss stuff) put these should give you an idea of what's in there.
Posted by jones at 11:07 AM | Comments (0)