Lecture Summaries for Polyhedral Computation       2012

Prof. David Avis                          Thursday  8:45 - 10:15        

      also check:  announcements        return to:  course home page

Basic reference:    Komei Fukuda's Polyhedral Computation FAQ


Oct 4: Course outline. We discussed the convex hull problem in two dimensions: convex hull and its solution using Graham's algorithm   notes   CH_alg_en   CH-alg_jp

Exercise: Refer to CH_alg notes (English or Japanese)
(a) Do exercise 2.7
(b) Write out a detailed pseudo-code for the function left(p,q,r)  which is true if and only if the points p,q and r in the plane form a left turn.
(It should be false if p,q and r lie on a straight line.)
Oct 11:  Basic definitions: polyhedron, vertex, face, facet, etc. The vertex enumeration problem. Solution by dictionaries and graph search. If you are not familiar with LP dictionaries, please read this excerpt from Chvatal's Linear Programming.  English or Japanese          notes     Please review these slides.
Exercise: Use the brute force method of Section 2 of the notes to classify all co-bases of the following system:
-x1 -x2 -x3 ≤ -6,  -x1  -2x3 ≤ -2,  -x2 ≤ -3, -x3 ≤ 2,  x1 +x2 +2x3 ≤  6
Your solution should include (1) a complete classification of all 10 subsets chosen in step 1 (2) a graph like Figure 7 (3) a sketch like Figure 2

Oct 18: The graph search method for vertex enumeration. Details of the adjacency oracle is in part 2 of these  notes
Be sure to read Section 3 on depth first search (DFS) and for more detail see the wiki page.
Exercise: Solve the problem for Oct 11 one more time using the graph search method and DFS. You may start from any of the feasible cobases you discovered doing the Oct 11 exercise.
In your report, you do not need to show every dictionary. However you should show the Adjacency oracle results for each dictionary as described in part 2 of the   notes
Oct 25: Graph search and reverse search. Review slides and this page for more information and history.
Exercises: Read carefully the tutorial especially Section 6 on trees.
1. Draw the reverse search tree corresponding to the output in Figure 6.3. Show the labelled trees at each node of the reverse search tree.
2. Let T be the tree in Figure 6.2 (do not include the dotted edge 15).
(a) Apply the local search function f to find the path from T back to the starting tree T*. Draw each tree along the path to T*.
(b) Work out completely all adjacent trees to T using the oracle Adj(T,i,j)
(c) Work out which, if any, of these adjacent trees are children of T in the reverse search tree.


Exercises for Oct 4,11,18,25  are due in class on Nov 1
Nov 1: Hans Tiwary guest lecture on Extension complexity.   notes
Exercises:  pdf
Nov 8: Hans Tiwary guest lecture on Extension complexity.   notes
Exercises:  pdf
Nov 15: Hans Tiwary guest lecture on polarity.   notes
Exercises: pdf
Nov 22: Kyoto university festival, no classes

Second report covers lectures on Nov 1,8,15 and is due in class on Dec 6
Nov 29:  Two person zero sum games games and Nash equilibria. Read Ch 15 from Chvatal: notes
Exercise: Do exercise 15.4 from the notes.
You should formulate the LPs for both players, and solve them using either lrs or lp_solve (See  announcements  )
Dec 6:  Second report is due. Atsuki Nagao will discuss problems on the first report.
Dec 13: Nash equilibria for general two person games: an application of vertex enumeration.  notes     paper
Exercise: Read the notes carefully, especially the example at the end.
Choose your own 3 X 2 matrices A and B and compute all Nash equilibria by the same method:
1. Compute all vertices of the two related polyhedron using lrs and make a table like that in the middle of page 3. Now choose one of the two vertex lists (shorter one is better) and for each vertex in that list compute the Nash equilibria (if any) using the other vertex list.
2. Check your work by downloading and running program nash from lrslib on your two matrices (see User's guide on lrslib home page for instructions)
Note: (Dec 20)
 I fixed the permissions for the DLL files. You need to run nash etc. from a command prompt (DOS window) found in the accessory folder in start menu.
The cygwin1.dll file must be in the same folder as nash. Please contact me and/or Atsuki Nagao by email in case of problems.
Dec 20: Guest lecture by Takashi Horiyama on folding and unfolding polyhedra.   slides
New Year break
Jan 10:  Guest lecture by Stefan Langerman on the Ham Sandwich Theorem.  slides
Exercise: Refer to slides 17-27 (Crossing free Red-Blue Matching).
1. Write down the algorithm concisely. (Note there are two cases depending on whether the total number of points is divisible by four or not.)
2. Draw a set of 26 points at random on a sheet of paper, and colour a random subset of 13 points red, the others blue.
3. Simulate the algorithm by hand to produce the crossing free red-blue matching.
Third report covers lectures on Nov 29, Dec 13, Jan 10 and is due in class on Jan 17
Jan 17:  Wrap up.  Final report is due.