Errata in the notes

I appeal for your help in fine-polishing the course notes as you re-read between now and the exams - particularly to root out typos and errors. I will add to this page whenever someone writes to me and I make a change to the notes. On page iv of the notes it will say something like "Last updated on December 3, 2015."

1. 03/12/15. Page 95. The "simple proof" of the Gibbard-Satterwaite theorem had a subtle mistake in the arguments of the last 3 paragraphs (either (i) or (ii) is true, but the final paragraph's argument was needing them both to be true). I have rewritten the argument in 3rd to last and last paragraph. Credit goes to Joe Wallace for noticing the issue.
2. 07/12/15/ Page 75. I have made a correction to the displayed equation in the proof of Lemma 16.4. Thanks to Alex Fisch.
3. 09/12/15 Thanks to Carla Groenland:
   - In 2.4: Typo: "optimality of the current solution. Recall that variables of the dual correspond to the Lagrange multipliers"
   - Just above 15.3, minimize changed to maximize.
   - In 16.4: Reference is changed to Lemma 16.4 instead of Lemma 17.1.
   - In 17.3: the knapsack equations changed so that at feasible solution: B=a^tx.
4. 17/01/16 Thanks to Matija Bucić:
   - 5.1 Second paragraph last sentence has surplus word that or lacks word note.
   - 18.3 second line of paragraph in step 1 is should be in
   - 21.2 Paragraph before example 21.4 last sentence
   - Lem 21.1 last sentence: the the
   Here I believe it would be helpful to point out that e(p) is the term which takes into itself the difference between auction systems in Lemma 21.1, I found it relatively hard to figure out what it is from the definition given and only after looking at examples did I figure out what it actually is.
   - Thm 21.2: the last term in rhs of (21.3) shouldn't include f(theta_1).
   - Also (21.3) is not necessarily equal to (21.4) (the term that we cancel out which evaluates at theta* and infinity might not be zero, problem is with the limits (0*infinity is not necessarily 0) for example if F(x)=(x-1)/x for x in [1,infinity) that term is strictly bigger than zero.
   Of course this doesn't “break the theorem” as this term is also independent of the auction style (it simply might not be zero).
   - I think it would be useful to add that theta* is independent of the auction style by the same bidder participation assumption, when we define theta*.
   - Also less relevant but I believe it might be useful to replace p with F^{n-1} in 21.4 as this might make it clearer the expression is really independent of the auction.
   - 21.3 First paragraph second row: n {mechanism!design - probably an uncommented latex reference
   - page 103 first line “other than” rather than “other that”
   - equation 21.5 rhs in the first term there is an extra right parenthesis
   - second paragraph page 103 “A mechanism is manipulable if the exist ” should be there instead of the
   - last equation in proof of theorem 22.2 there is an f missing (there should be an u(f(theta_i,theta_{-i}), theta_i)
   - paragraph with clark pivot rule on page 105 at two places there is v_j(f(theta)) instead of v_j(f(theta), theta_j), as v_j has two parameters.
   - Page 107 third paragraph 4th row, one to is extra “declare θi = u to so as to maximize”
   - Paragraph with participation fee: “then his expected payment is be”
5. 27/01/16. Thanks to Yoni Berger: * Lecture 12, page 57, section 12.4 - is the matrix C1 correct? Why is there a 1 in all diagonal entries? If they both pick phone b for example is it certain that they will not connect? * Lecture 4, page 20 section, 4.2 - last paragraph of the section before Gomory’s cutting method. Should three occurrences of ’n-m’ be replaced my ‘m’?  * What is Newton’s method referred to in Section 12? * Suggested typos: * Lecture 2, page 8, section 2.3 Word ‘appropriately’ written with no apparent context. * Lecture 12: page 54, section 12.1 - y printed instead of lambda for dual objective function * Lecture 17 Section 17.2 page 78 Definition of \bar v is slightly wrong. * Lecture 18 page 85: Before the words Otherwise stop it says 'goto step 1' - should be something like 'go to step 2.'  At the end of step k it says 'goto step k+1' with space missing. * Page 86: Section 18.4 'Suppose a subset of players, S, has an objection to payoff x because S would be have...' Delete the word 'be' 

Lecture 23

In the final lecture I spoke further about auction design, and then showed how the same ideas can be used to design a mechanism for a problem in which agents will share a facility (or a so-called club good). The mechanism receives declarations of agent types, $\theta_1,\dotsc,\theta_n$, and then chooses a size for the facility, $Q$, and extracts payments from the agents to cover its cost, $c(Q)$.

Agents with small $\theta_i$ will not find it worth joining the club and will not be made to make any payments. The analysis harkens back to earlier lectures, in that Lagrangian methods are employed, and a pivoting type algorithm is used to make adjustments to the payments. An agent will find it profitable to join the club iff $\theta_i+\lambda g(\theta_i)\geq 0$, where $\lambda$ is a Lagrange multiplier for the constraint that expected payments cover expected facility cost. The case $\lambda=\infty$ corresponds to maximizing the expected payments taken from the agents.

I gave a talk on this work at London School of Economics: Mechanism Design for a Service Provided in the Cloud. If you view this talk you will see how I managed to work into my talk the playing of the song ‘non, je ne regrette rien’ (‘no, I regret nothing’) (as sung by Edith Piaf).

Exam rubric

Lecturers have been asked to tell students what the rubric will be for the examination in June. For this course it will be:

Attempt no more than FOUR questions.

There are SIX questions in total.

The questions carry equal weight.

Part III essays

This is just a reminder for those who see it that I will discuss Part III essays in my office D1.13 tomorrow, Tuesday, at 3.30pm. 

Lecture 22

I appreciate with hindsight that there was a lot to take in this this lecture. The punchline was that for an optimal auction (maximizing the seller's expected revenue), the fact that we want a direct revelation mechanism forces:
\[ P_i(\theta_i) = \theta_iV_i(\theta_i)-\int_{\theta_i^*}^{\theta_i} V_i(w)dw\tag{1}
\]
where $P_i(\theta_i)$ is bidder $i$'s expected payment (and $V_i(\theta_i)$ is his probability of winning the item) given that his valuation for the item is $\theta_i$, and thus that
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] So the auctioneer should arrange that for every $\theta_1,\dotsc,\theta_n$, he maximizes $\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)$. This simply means awarding the item to the bidder with the largest non-negative value of $g(\theta_i)$, and not awarding the item to anyone if no $g(\theta_i)$ is positive.

This becomes more interesting when agents are heterogeneous, so that $F_i$ differ. The anaysis alters only slightly, becoming
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g_i(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] For example, if $n=2$ and $\theta_1,\theta_2$ are independent and distributed $U[0,1]$ and $U[0,2]$ then $g_1(\theta_1)=2\theta_1-1$ and $g_2(\theta_2)=2\theta_2-2$. So the optimal auction is one in which

(a) Bidder 1 wins the item if $2\theta_1-1\geq 2\theta_2-2$ and $\theta_1\geq 1/2$.
(b) Bidder 2 wins the item if $2\theta_2-2> 2\theta_1-1$ and $\theta_2\geq 1$.
(c) Otherwise the item is not won.

Appropriate payments for the auction design have to be worked out using (1). However, another way to figure the payments is by the VCG mechanism. This boils down to agent $i$ paying, when he wins, the least $\theta_i$ for which he would still win. E.g. in case (a) bidder 1 should win, and pay $\max\{\theta_2-1/2,1/2\}$.

Lecture 21

I mentioned

The ultimate prize for a Game of Thrones fan: the chance to become one of the many, many characters killed off by George RR Martin in the books that are inspiring the TV series. And now two fans have paid $20,000 each in an online charity auction to receive the honour of a character being named after them in the next novel – and seeing them "certainly meet a grisly death". (from the Guardian 12/06/14)

and for the sale of the Roman empire by auction, see: An Early Example of the “Wmner's Curse” in an Auction.

Lecture 20

I have thought that existing proofs of the Gibbert-Satterthwaite theorem are necessarily complicated and hard to explain. I was delighted to find a recent paper Yet Another Very Short Proof of the Gibbard-Satterthwaite Theorem, by Ville Korpela, October 2015, which I have adapted to provide the proof in section 20.3 and which I presented in today's lecture. I have added to pages 96-98 of the notes the proof that was given to students last year. You can compare and see which you think is easier to understand.

I did not prove Arrow's impossibility theorem. You can see at the link that its proof is quite long-winded.

It may at first seem a bit strange in 20.1 to call $f$ a social welfare function. Perhaps "social preference function" sounds more natural. However, in general, a social welfare function is a function which allows us to compare any two alternatives and say which is better, or that the are equal. In other contexts this can be done because the social welfare function associates to alternative $a$ a real number, say $f(a)$, and then alternative $a$ is preferred to $b$ iff $f(a)>f(b)$. Arrow's set up is more general,because $f$ outputs a linear order on the set of alternatives, $A$. So $a$ is preferred to $b$ iff $a\succ b$, where $\succ=f(\succ_1,\dotsc,\succ_n)$.

I have pretty much finished writing the lecture notes up to the end of the course, Lecture 23. The notes now include a table of contents and index. Since this year I have made a new reworking of the material I would appreciate hearing from you about any typos that you find in the notes, or things which you think could be better explained, while maintaining conciseness. I am deleting this year the topic of stable matchings which was originally listed in the draft schedules.

Lecture 19

I had worried that my proof of Theorem 18.2 was not sufficient. (I have not taken this from any textbook, but made it up.) On reflection, I think that it is. Do you agree? It is not the shortest proof of this result since it relies on first understanding the algorithm for finding a nucleolus on page 85. However, since we have that algorithm, we may as well use it. Notice that this algorithm does two things: it proves the nucleolus exists, and it shows that the nucleolus is unique. Another way to show the nucleolus exists is by appealing to compactness of the set in which we are looking for the lexicographic minimum.

I should have mentioned that the set of imputations might be empty. However, it is non-empty if the game is superadditive. There is a simple $x$ that will work as an imputation. Can you guess it? I will make this a question for Examples sheet 3. Notice that in (P1) on page 85 there is no requirement that $x$ be an imputation, only that it be efficient, in the sense that $\sum_{i\in N} x_i = v(N)$.

There are some very nice notes and slides for 12 lectures on cooperative games, by Stéphane Airiau. His notes for lectures 4 and 5 are particularly relevant to what I have presented about bargaining games, core and nucleolus. You might enjoy browsing the slides for a second view and to see more examples.

Lecture 18

The slides used in today's lecture are: The disputed garment problem: the mathematics of bargaining and arbitration. (It is best to view this by downloading the file and then viewing with an app like Adobe Acrobat, so that you can see the slide transitioning.)

Lecture 17

It was a pity my coloured figure to explain Sperner's lemma in $\mathbb{R}^2$ did not show up well on the overhead projector. On page 82 of the notes I have now put a version with  colours black, white and grey. I hope you can understand the lemma and its proof when you review this. You should see that the proof of the Brouwer fixed point theorem (via Sperner's lemma) and the Lemke-Howson algorithm use a common idea that a graph in which all vertices have degree 1 or 2 must have an even number of vertices of degree 1, and that given one vertex of degree 1 it is possible to find another by following a unique path.

Along each side of the large triangle there is an odd number of edges whose two endpoints are differently coloured. Entering along the base across such an edge and following a path crossing edges which are similarly coloured, we must, with at least one choice of initial entry edge, reach a rainbow triangle. Notice that this also proves that the number of rainbow triangles is odd. In this example there are 3 rainbow triangles. Only one is found by a following a path entering at the base. What happens in the above if you try to enter along an edge on the long right side whose endpoints are red and blue?

Notice that a linear programming problem can be formulated as linear complementarity problem and solved using Lemke's algorithm. (Quadratic programming with $D=0$.)

I have made some corrections and improvements at the bottom of page 80 of the notes. Here $w,z$ needed to be swapped, and I have tried to improve the explanation.

The formulation of a knapsack problem as a linear complementarity problem in 17.3 I took from the paper On the solution of NP-hard linear complementarity problems by Judice, Faustino and Martins Ribeiro, 2002. The authors conclude that Lemke's algorithm is not a good way to solve this LCP.

Lecture 16

Consider the decision problem: "Given a two-player game, does there exist a Nash equilibrium?" It is in NP, since given as a certificate a candidate equilibrium we can check that the answer is yes in polynomial time. But we don't actually need to do this, since by Nash's theorem the answer is always yes!

It is therefore more helpful to rephrase the question as a search problem:  NASH: "Given a two-player game, either find a Nash equilibrium or output "no" if none exists." This  problem can be solved in polynomial time by a nondeterministic Turing machine by examining all possible supports for the equilibrium strategies, so it is a problem in NP. It is not known whether or not NASH is NP-complete. However, many other problems are NP-complete, such as 2NASH: "Given a game and a Nash equilibrium, find another one, or output “no” if none exist."

Notice that the Lemke-Howson algorithm described today is not a polynomial time algorithm. Just as the the Klee-Minty example for the simplex algorithm, there are examples in which the length of the Lemke-Howson path grows exponentially in the size of the game. I will say more about the algorithm in the next lecture.

There is a good lecture by Papadimitriou on the question of: Complexity of Finding a Nash Equilibrium. He defines PPAD as the class of all search problems which always have a solution and whose proof is based on the parity argument for directed graphs. This includes the problem of finding a Nash equilibrium, where the proof is based on the Lemke-Howson algorithm. In fact, the other proof, based on the Brouwer fixed-point theorem, is also in this class, since a proof of the Brouwer fixed-point theorem uses Sperner's lemma, which is itself based on a parity argument in a directed graph.

Lecture 15

The normal form games studied today are one in which both players take actions simultaneously. A sequential game, like chess, can in principle be made into a normal form game, but each pure strategy for white would need to be a complete specification of the moves white would make in each possible board position that could be reached by prior moves of white and black playing in some way. The number of pure strategies for white would need to exceed the Shannon number, which is the number of different games of chess that can be played. It is thought to be about $10^{120}$.

Examples sheet 2

Examples sheet 2 is now available. I hope you find these questions interesting.

Lecture 14

The re-edited proof of the PTAS for knapsack that in now on page 59 of the notes looks to me to be correct. We need to say that when we fill up after $K$ using the greedy algorithm we use only items with values no more than values in $K$. This ensures that when $K=H$, where $H$ is the $m$ most valuable items in $O$, we find the bound $v(O)\leq v(H\cup G)+v_j$ and we can be sure that $v_j\leq v(H)/m\leq v(O)/m$.

In the Euclidean case of the travelling salesman problem distances are symmetric and satisfy a metric (i.e. triangle inequality). This restriction of the problem is in APX (while the general problem is not). It is easy to find a 2-approximation algorithm in the Euclidean case (a question on Examples sheet 2.) This can be improved to a 3/2-approximation algorithm due to Christofides in 1976. An even better approximation algorithm was found in 2011. It is a 1.4999999999999999999999999999999999999999999999999996-approximation algorithm (compared to Christofides's 1.5). See Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem.

An excellent web site with history of the TSP and many facts about it is The Traveling Salesman Problem at the University of Waterloo.

There is a very nice demo of simulated annealing applied to the travelling salesman problem by Schneider, The Traveling Salesman with Simulated Annealing, R, and Shiny. I showed this in today's lecture.

A Mathematica program running Nearest neighbour, 2OPT and Simulated annealing is here.

It is common to speak of simulated annealing as being a meta-heuristic, because it is readily applicable to a large variety of problems. Other meta-heuristics are genetic algorithms, ant colony optimization and particle swarm optimization. (Many heuristics try to draw on something that nature appears to do well.)

Lecture 13

I have rewritten Section 13.1 of the notes (arguments for a PTAS for the knapsack problem.) I will discuss this in the next lecture. I have also added notes for Lectures 14 and 15 (which may be subject to small revisions.)

As some of us talked of after the lecture, the branch and bound algorithm can be generalised to the alpha-beta pruning algorithm, which lies at the heart of programs that play strategic board games like chess and reversi.

When looking for a branch and bound tool I might show you (see next paragraph), I came across an article, Branch And Bound—Why Does It Work?, in which the author addresses the question of why it is difficult to prove a concrete result about average running time of the branch and bound algorithm. I once spent some time trying to investigate this question myself, without any success. The author makes the provocative comment that doing something on this problem rings bells in ones mind with the famous Collatz conjecture.

I showed you briefly this nice interactive branch and bound solver for the knapsack problem, by Jacopo Corbetta, which can help you to understand the algorithm. I suggest pressing "add item" until you have 7 items, and then put max weight = 20. Click on "start solving" and then choose where to "branch", successively, until you find the optimal solution. Here is the start of the tree. Notice that branches of increasing depth are indicated by indentation to the right.

Maximum weight: 

v1 w1 
v2 w2
v3 w3
v4 w4
v5 w5
v6 w6
v7 w7

Solution

Current best value: zcur = (none)

Possible branches: 3

Step 1a Branch constraints: x6=0 
Optimal value for the relaxed problem: 25.714285714285715 (remaining weight: 0)

x: 1111100.7142857142857143

Step 0 Branch constraints: (none)
Optimal value for the relaxed problem: 25.833333333333336 (remaining weight: 0)
x: 111110.83333333333333340

Step 2a Branch constraints: x5=0 x6=1 
Optimal value for the relaxed problem: 25.57142857142857 (remaining weight: 0)
x: 1111010.5714285714285714

Step 1b Branch constraints: x6=1 
Optimal value for the relaxed problem: 25.8 (remaining weight: 0)
x: 11110.810

Step 2b Branch constraints: x5=1 x6=1 
Optimal value for the relaxed problem: 25.75 (remaining weight: 0)
x: 1110.75110

A Big Result On Graph Isomorphism

A very interesting thing was mentioned in the BBC radio programme: namely that on 4 November, 2015 László Babai announced a new result for the graph isomorphism problem. You may recall that this problem is conjectured to be NP-intermediate, being neither in P or NP-complete. The new result is that there is an quasi-polynomial time algorithm for this problem. This shows that the problem is much closer to being in P than to being NP-complete. See A Big Result On Graph Isomorphism.

P vs NP on Radio 4

Yesterday morning the subject of P vs NP was discussed on BBC Radio 4's In Our Time.

"Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. ..."

You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.

Lecture 12

The slides I used today to talk about the rendezvous problem are linked here. The paper is

R. R. Weber, Optimal symmetric rendezvous search on three locations, Math Oper Res., 37(1): 111-122, 2012.

It was in solving this problem that I first came to study semidefinite programming. I am fond of this paper because of the way it employs a range of mathematical tools on the way to proving the main theorem. Indeed, I today discovered that there is an AMS review of this paper which says, "The author dedicates many pages to the proof of the theorem, utilizing multiple ideas from probability theory, game theory, linear algebra, linear programming, and semidefinite programming."

I mentioned today the class APX, consisting of optimization problems that are approximable, in the sense that there exists a polynomial time algorithm which can always find an answer that is within a fixed multiplicative factor of the optimal answer. One example of an APX problem is the travelling salesman problem with distances satisfying the triangle inequality. For this problem there exists a 2-approximation algorithm based on the efficient solution of the minimum spanning tree problem. (This will be a question for you on Examples sheet 2.) This problem is also APX-complete, in that it is as hard as any other in problem in APX.

Another APX-complete problem is minimum vertex cover. This also has a 2-approximation algorithm: just find a maximum matching and then include in the vertex cover both endpoints of the edges in the matching. Do you see why this works?

We now know about P, NP, NP-hard, NP-complete and APX. There is a huge "zoo" of complexity classes. The entertaining complexity zoo web site lists 498 complexity classes that have been defined by researchers.

Wikipedia articles

In these blog entries, I often provide links to Wikipedia articles. In my experience, Wikipedia articles tend to be rather good in the fields of computer science and operations research. They have been refined by experts and often give introductions to topics that are illuminating while remaining concise. I particularly like what these articles contain about the history of methods. For example, who was Dijkstra, for whom Dijkstra's algorithm is named? (One might guess from the name that he must be a Ducthman!)

One needs to be critical, but errors tend to be few since many eagle-eyed persons have poured over the articles. For example, the articles on Max-flow min-cut theorem and Konig's theorem are interesting to read in conjunction with Lecture 10.

Lecture 11

At the start of today's lecture I explained the Hungarian algorithm, which is a polynomial time algorithm for solving the assignment problem. My emphasis was on explaining why it works. In practice the algorithm looks rather different. The fact that one is adjusting node numbers and solving maximum matching problems is rather hidden from view.

You might like to read this nice tutorial on the Hungarian algorithm and read through the simple Example 2 on pages 18-27.

The algorithms in Lecture 11 are all polynomial time algorithms: Bellman-Ford, Dijkstra's and Prim's algorithms. They do involve numbers $c_{ij}$, but the the calculations that must be done with these numbers, such as adding (to find $c_{ij}+\lambda_j$) and comparing (to find $\min\{c_{it},c_{ij}+c_{jt}\}$) can all be done in time that is polynomial in the size of the input, as measured in numbers of binary bits. This is why running time is depends most crucially on the number of vertices $|V|$ and number of edges $|E|$.

One should be aware that for graphs with special structure, perhaps very sparse in edges, there exist specially tailored versions of some of our algorithms, which have better running time than those quoted in this lecture for a complete graph where $|E|=|V|^2$.

Examples sheet 1 #4

There was some question in the class about a part of the argument. Consider \begin{align} \max\;\{\; & 0^T x:\,Ax=b,\, x\geq 0\;\} \tag{1} \\ \min\;\{\; & y^T b:\, y^T A\geq 0^T\;\} \tag{2} \end{align} If (1) is feasible then for feasible $x,y$ we have $y^T b= (y^T A) x\geq 0$, so (2) is bounded.

On the other hand, if (2) is bounded then it is feasible and bounded. The strong duality theorem for linear programming states that (1) is feasible and bounded if and only if (2) is feasible and bounded. So (1) is feasible. This is enough to answer the question.

But how do we prove strong duality for linear programming? One way to prove it is via Farkas Lemma, which in the context of this question would be cheating. Another way is by appeal to the supporting hyperplane theorem and the sufficient conditions (satisfied by linear programs) for $\phi(b)$ to be convex.

I now think (c) of this question would be better phrased as "The Strong Duality theorem for linear programming states that if a linear programming problem is both feasible and bounded, then so is its dual." Show that this implies Farkas Lemma."

Lecture 10

I have been working on the notes for this lecture and have now added several further figures. Please make sure you have an up-to-date copy of the notes, as there were some errors in previous versions.

I will talk about the Hungarian algorithm for the assignment problem at the start of next lecture.

I mentioned that in a problem where all edge capacities are integers the Ford-Fulkerson algorithm runs in time $O(|E|\cdot f)$, where $f$ is some bound on the total flow. If edge capacities are not integers, one can still apply the Ford-Fulkerson algorithm, but it is not guaranteed to converge. There are examples in which one can increase flows on augmenting paths by ever smaller and smaller amounts, but not even converge to the optimal flow.

To understand the proofs of Hall's marriage theorem and Konig's theorem, you really need to sit down and carefully study for yourself an example, as I have now provided in Figure 12.

There are many nice applications in which the min-cut max-flow theorem can be used to obtain other results, by applying it to the right network. Another example of this is Menger's theorem: Let $G$ be a finite undirected graph and $x$ and $y$ two distinct vertices. Then the minimum number of edges whose removal disconnects $x$ and $y$ is equal to the maximum number of pairwise edge-independent paths from $x$ to $y$. This theorem is proved similarly to Konig's theorem. 

Lecture 9

The transportation problem and assignment problems are important problems, both practically and theoretically. They are simple without being trivial, and therefore are good problems on which to test new ideas about algorithmic methods.

I mentioned the fact that the Hirsch conjecture for the $n\times m$ Hitchcock transportation problem polytope states that no more than $m+n-1$ pivots should be needed to move between any two basic feasible solutions.

The diameter of a specific transportation polytope depends on the values of $n$, $m$, $s_i$s and $d_j$s, all integers. The Hirsch conjecture can be checked combinationally for small value of these. That has been done and the Hirsch conjecture has indeed been found to hold. (We allow pivot steps for which $\sum_{ij}x_{ij}c_{ij}$ does not decrease.)

A recent seminar on the subject is Kim's Transportation problem and the diameters of transportation polytopes (2015). Kim says that Hurkens has proved the upper bound $4(m+n-1)$. There is a folklore that Hurkens proved $3(m+n-1)$ in 2007, but this is in an unpublished paper. It is not hard to prove that the Hirsch conjecture holds for the special case $n=2$ and general $m$. I cannot recall whether or not it has been shown for $n=3$.

The assignment problem polytope has diameter 2 because every permutation is the product of two cycles, and applying a cyclic permutation to an assignment corresponds to a pivot step in the assignment problem. See On the assignment polytope, by Balinski and Russakoff.

The network simplex algorithm which we used in today's lecture to solve the transportation problem is not a polynomial time algorithm, but in practice it works very well. There do exist simplex-like pivoting algorithms for the transportation problem that run in polynomial time. I will explain next time a polynomial time algorithm for the special case of the assignment problem. This is the Hungarian algorithm, which solves the $n\times n$ assignment problem in time $O(n^3)$.

Lecture 8

The minimum cost flow problem (MCFP) is important because a huge number of problems are special cases of it. We saw in 8.5 that the longest-path problem can be viewed as a MCFP and leads to the critical path method, one of the oldest of all operational research techniques.

We have studied the solution of the MCFP by the network simplex algorithm. As with a general linear programming problem, the possibility of making a bad choice of pivots can give the algorithm a worse that polynomial running time. However, there do exist simplex algorithms which do run in polynomial time. See

James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming 78: 109–129.

Suppose $n$ and $m$ are the numbers of vertices and edges, respectively, and each cost is either $\infty$ or an integer bounded by $C$. Orlin describes an simplex-like pivoting algorithm with running $O\bigl(\min(n^2m \log nC, n^2m^2 \log n)\bigr)$.

Lecture 7

You will have seen that the details of the Ellipsoid algorithm are really quite intricate. I have tried to show you the key ideas in Lemmas 7.1-7.3, but have not dealt with the issue of approximating square roots in polynomial running time. If you have a question about the explanation or think you see an error in the notes, please let me know so I can fix it.

I think the proof of Lemma 7.3 is particularly cute for the way it uses the primal-dual theory of linear programming to show that $\text{P}=\emptyset\implies \text{P}_\epsilon=\emptyset$. Question 10 on Examples Sheet 1 is similar in spirit.

Remember that the importance of the Ellipsoid algorithm lies in its theoretical rather than practical. In practice, linear programs are solved by high quality implementations of the simplex algorithm or by an interior point method like Karamakar's method.

In Lemma 7.2 we used the fact that $Q\subset \mathbb{R}^n$, the convex hull of $n+1$ vectors, $v^0,v^1,\dotsc,v^n$, that do not lie in the same hyperplane has
$$ \text{vol}(Q)=\frac{1}{n!}\left| \det \left( \begin{array}{ccc} 1 & \cdots & 1 \\ v^0 & \cdots & v^n \end{array} \right)\right|. $$ The proof of this result is not for our course, but if you are interested see A Note on the Volume of a Simplex, P. Stein The American Mathematical Monthly Vol. 73, No. 3 (Mar., 1966), pp. 299-301

Lecture 7 postponed

Unfortunately I had to cancel our lecture on Friday 23 October because of illness. I am hoping to be well enough to lecture on Monday. I have taken the opportunity to make some small corrections and refinements to the lecture notes for Lecture 7.

Lecture 6

The proof that the Ellipsoid algorithm can solve linear programming in polynomial time is due to Leonid Khachiyan (1979). This discovery took place a full 20 years after the invention of the simplex algorithm. Today we sketched its main idea. In the next lecture we will be looking at some of the details.

I mentioned today some examples of problems in different complexity classes. Let me recap here:

P includes "Is there a path from $i$ to $j$ in this graph with cost $\leq k$?", 2SAT and "Is the set $P=\{x : Ax\leq b\}$ nonempty?"

NP-complete includes SAT, 3SAT, Subset Sum, Hamiltonian Path, Travelling Salesman Decision Problem ("Does there exist a tour of length $\leq k$?"), and Subgraph Isomorphism.

NP-hard, but not in NP includes TSP optimization problem ("What is the shortest TSP tour?") and the Halting Problem. Note that is it wrong to say, as some do, that the travelling salesman problem of finding the best tour is NP-complete. It is not NP-complete. It is NP-hard. In general, optimization forms of NP-complete decision problems should be spoken of as being NP-hard.

NP, but not in P or NP-complete, is conjectured to include Graph Isomorphism. If this could be proved then it would follow that P$\neq $NP.

EXAMPLE SHEET 1. Let me make some remarks on the examples sheet which you should now be attempting.

Q10. Think about the dual to "maximize $0^T x$ s.t. $Ax\leq b$.

Q11. Here you are being asked to show SAT $\leq_p$ 3SAT. So you need to find a way to make a polynomial time reduction from a SAT instance to a 3SAT instance.

Q12(b). Here are you being given some hints as to how to make a polynomial time reduction from SAT by which to show SAT $\leq_p$ Hamiltonian Path Problem.

A Brief History of NP-Completeness, 1954–2012

David S. Johnson has written a paper called A Brief History of NP-Completeness, 1954–2012. The year 2012 was the 100th anniversary of the birth of Alan Turing and the 40th anniversary of Richard Karp's important paper detailing 23 NP-complete problems. If the subject of NP-completeness and P$=$NP interests you, then you might enjoy reading this paper about the history of computational complexity theory. 

Lecture 5

I had not anticipated that it would take so long to describe the basic elements of complexity theory and therefore was not able to finish all that I had put in the notes for Lecture 5. However, this is of no matter. Next time I will talk about the important question of whether or not P$=$NP.

Computational complexity theory is a very large subject, of which this lecture can only scratch the surface. You should aim to understand the definition of problem classes P, NP, NP-hard and NP-complete. There are other complexity classes, such as PSPACE (problems that can be solved using memory space that is polynomial in the size of the problem) and EXPTIME. It is known that P $\subseteq$ NP $\subseteq $PSPACE $\subseteq $EXPTIME, with at least one of these inclusions being strict, but it is not known which.

I mentioned the famous book, Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson. This is perhaps the most cited reference text in all of computer science. For this book they received received the 1979 Lanchester Prize from the Operations Research Society of America.

The following few remarks are certainly non-examinable, but you might find them interesting.

1. In the figure on page 24 of our notes one can see that there are potentially problems which are NP-hard but which are not NP-complete. Optimization problems are in this class. That is, "Does there exist as solution to a given travelling salesman problem with path length $\leq k$" is NP-complete. However, the harder problem: "Find the minimum length travelling salesman path" is  NP-hard and not in NP. One reason it is not in NP is that it is not a decision problem. An example of a decision problem that is NP-hard but not in NP is the halting problem: "given a program and an input, does the program terminate when run on this input?"

2. Problems that are in NP but neither in P or NP-complete are designated NPI (the letter I standing for "intermediate"). It has been proved that if P$\neq$NP then NPI problems must exist. But no natural ones are known. It is suspected that graph isomorphism is NPI, since it has not been proved to be either in P, or NP-complete. This is the problem of deciding whether or not two graphs are isomorphic. On the one hand graph isomorphism is in P for many special types of graph (such as planar ones). On the other hand, the subgraph isomorphism problem is known to be NP-complete. This is the problem of deciding whether or not one graph contains a subgraph which is isomorphic to a second graph.

3. Sometimes changing a problem very slightly can change its complexity. For example, 2SAT is the Boolean satisfiability problem in which each clause is restricted to have just two literals. This problem is in P, whereas 3SAT is NP-complete.

4. The question of whether or not it is true that P$=$NP is unlikely to be solved soon. Research success, such as it is, has succeeded only in explaining why certain proof ideas must be incapable of resolving this question. There are thousands of theorems in the research literature which are stated in the form "... is true, unless P$=$NP".

Lecture 4

On page 20 of the notes the first tableau should have $a_{21}=-2$. In fact it does in the notes, but not in the overhead slide I was using.

It is not obvious that Gomory's cutting plane algorithm should terminate. If interested, you can read this proof that it terminates.

The paper I mentioned about using linear programming to find a potential function needed for proofs in an online bin packing problem is

 E.G. Coffman, Jr, D.S. Johnson, P.W. Shor and R. R. Weber. Markov chains, computer proofs, and average-case analysis of best fit bin packing. In Proc. 25 Annual ACM Symposium on Theory of Computing, San Diego, May, pages 412-421, 1993.

I had forgotten the date. Obviously computers are now much more powerful. It might be possible to extend the table in this paper, and perhaps formulate some conjectures concerning which $\{j,k\}$ lead to bounded or linear waste.

I mentioned that CPLEX is one of the leading commercial packages for linear programming. One can solve problems of medium size quite quickly with Mathematica. I have used Mathematica for problems of a few hundred variables and constraints.

Non-degenerancy assumptions

I said we would make two assumptions.

(i) The rows of $A$ are linearly independent and thus it has rank m. (If some rows are linearly dependent then a constraint can be removed without changing the feasible set).

(ii) Every set of $m$ columns of $A$ are linearly independent. (If some columns are linearly dependent then one of the corresponding variables can be removed.)

Thanks to a student query, I have thought more about this. What are we trying to achieve with these assumptions? Suppose $x$ is a BFS with support of size $m$, but the columns of this support are linearly dependent, so $Ay=0$ where $S(y)\subseteq S(x)$. Then by considering $x'=x+\epsilon y $ and increasing $\epsilon$ away from $0$ (in either the positive or negative direction) until some component of $x'$ becomes $0$, we see that it is possible to find a new feasible solution $x'$ such that $S(x') < m $. This is known as a "degenerate solution", i.e. there is a solution to the $m$ constraints $Ax=b$ in which strictly less than $m$ components of $x$ are nonzero. In the simplex tableau this would evidence itself by there being a $0$ in the rightmost column of the tableau. This is more than we can expect in general. Perturbing $A$ slightly, this should not happen. For the purposes of giving an algebraic explanation of the simplex algorithm we want $A_B$ to be non-singular. Degeneracy can also occur in dual solutions. This would be evidenced by a $0$ occurring in the bottom row of the tableau, in the column of a non-basic variable. It would be better to restate our assumptions as follows (and I will amend the notes.)

(i) The rows of $A$ are linearly independent and thus it has rank m.

(ii) Every set of $m$ columns of $A$ are linearly independent.

These assumptions rule out degeneracies of the following types: that we might have $Ax+z=b$ in the primal for some $(x,z)$ having less than $m$ non-zero components, or in the dual we might have $\lambda^TA-w^T=c^T$ for some $(\lambda,w)$ having less than $n$ non-zero components.

Degeneracy is not really a problem in practice, but it is with degeneracy that cycling can occur. In the example in lectures the pivot column is being chosen as the one with the most negative entry. One way to avoid cycling is to choose amongst pivot columns in a different way: by preferring the candidate whose variable has the smallest index (Bland's rule). You can check with that this pivot column selection rule the tableau considered in lectures does not cycle.

Lecture 3

The simplex algorithm is due to George Dantzig. In his paper on the origins of the simplex algorithm he writes:

"In the summer of 1947, when I first began to work on the simplex method for solving linear programs, the first idea that occurred to me is one that would occur to any trained mathematician, namely the idea of step by step descent (with respect to the objective function) along edges of the convex polyhedral set from one vertex to an adjacent one. I rejected this algorithm outright on intuitive grounds - it had to be inefficient because it proposed to solve the problem by wandering along some path of outside edges until the optimal vertex was reached. I therefore began to look for other methods which gave more promise of being efficient, such as those that went directly through the interior."

This is interesting because Dantzig says that the simplex method is something that any trained mathematician would think of - but that that on first sight it appears to be inefficient.

In practice these days computers solve problems with 100,000s constraints and variables. There is a nice on line simplex method tool which you might like to use to check answers that you obtain by hand when doing questions on Examples sheet 1. There is also a very nice program here, which runs under Windows.

http://trin-hosts.trin.cam.ac.uk/fellows/dpk10/IB/simple2x.html

It was written by Doug Kennedy at Trinity.  It takes the hard labour out of performing pivot operations and it may be configured to prompt the choice of pivot elements, or to solve problems automatically. 

Examples sheet 1

I have uploaded Examples sheet 1. This contains questions on Lagrangian methods, linear programming and computational complexity. We will have a session at which I will discuss these questions on Tuesday November 3: 16:00-17:30 in MR14.

Lecture 2

We did not prove Theorem 2.1 (Supporting Hyperplane Theorem). It is an obvious theorem, but actually fairly tricky to prove. The proof can be found in Boyd and Vandenberghe 2.5. One first proves the "separating hyperplane theorem" which says that two non-intersecting convex sets can always be separated by a hyperplane. The supporting hyperplane theorem follows by applying the separating hyperplane theorem to two specific sets. One is the set of points  $\{(c,y): y>\phi(c), c\in \mathbb{R}^m\}$, and the the other is the set consisting of the single point $(b,\phi(b))$. The first of these sets is convex if $\phi$ is convex.

I have revised the proof of Theorem 2.4 to make it shorter, but I believe it is still clear.

I did talk to Section 2.5 today. I will return to the subject of shadow prices another time.

Water-filling solution. The problem I referred to as having a "water-filling solution" is motivated by a problem in  information theory. Suppose one is trying to apportion a constrained amount of total transmission power across a number of noisy Gaussian communication channels. In channel $i$ the received signal is $Y_i=x_i+Z_i$, where $x_i$ is input signal, for which on-average $x_i^2=p_i$, and $Z_i\sim N(0,n_i)$. When the power to noise ratio in the $i$th channel is $p_i/n_i$ then the capacity of this channel is proportional to $\log_2(1+p_i/n_i)$. The problem of maximizing the $\sum_i\log_2(1+p_i/N_i)$ is that of distributing a fixed amount of power $\sum_ip_i=P$, say, across multiple channels so as to maximize the total communication capacity of these channels, i.e.  the rate at which information can be reliably transmitted. 

Lecture 1 homework

1. Consider $P_b$: minimize $f(x)=-x$, in two cases:

(a) $h(x)=\sqrt{x}$, $b=2$;

(b) $h(x)=x^2$, $b=16$.

What happens when you try to solve these problems using Lagrangian methods? In each case, find $\phi(b)$ and explain whether strong duality holds.

 2. Given $a_1,\dotsc,a_n>0$,
 \[
 \begin{align*}
\text{minimize}\ &- \sum_{i=1}^n \log(a_i+x_i)\\[4pt]
 \text{subject to } & x_1,\dotsc,x_n\geq 0\text{ and } \sum_{i=1}^nx_i =b.
 \end{align*}
 \]
The optimal $x$ corresponds to one that can be found by a so-called `water filling algorithm'. Imagine placing bars of heights $a_i$ side by side in the fashion of a histogram and then flooding above these bars so as to cover area of $b$. Draw a picture to illustrate this idea.

Biography of Alan Turing launched today

Alan Turing will be mentioned on our course for the Turing Machine (Lecture 5). At 6:60am today on the Radio 4 today programme I heard: "Alan Turing was the British mathematician who broke German codes at Bletchley Park during World War II. He committed suicide after he was prosecuted for homosexuality. A new biography is being published of Turing's life ­ by his own nephew Dermot Turing. It was launched yesterday in ­GCHQ."

This from the Glouceshire Echo:

"A book commemorating the life of renowned codebreaker Alan Turing will be officially launched at GCHQ.

Prof: Alan Turing Decoded, written by Turing's nephew Sir Dermot Turing, will be unveiled at the government's Cheltenham-based listening hub today.

It celebrates Turing's work as a mathematician, codebreaker, computer scientist and biologist.

Alan Turing made a crucial contribution to the cryptanalytic success of GCHQ's forerunner, the Government Code and Cypher School, at Bletchley Park during World War II."

Read more: http://www.gloucestershireecho.co.uk/8203-Biography-legendary-codebreaker-Alan-Turing/story-27946199-detail/story.html#ixzz3o3MsHjrG

The Secret Rules of Modern Living: Algorithms

ALGORITHMS feature centrally in operations research. Last night I watched this fun program by Marcus du Satuoy, with the title "The Secret Rules of Modern Living: Algorithms".

Professor du Sautoy discusses many things that we will meet in our course, such as the Travelling Salesman Problem and the Gale-Shapley algorithm for stable matching.

It is on BBC iPlayer for just 20 more days. I recommend that you catch it.

http://www.bbc.co.uk/programmes/p030s6b3




The program begins with the example of a face recognition algorithm.

"From internet shopping to the airport runway, algorithms are everywhere in modern life. They are behind the success of tech giants like Google, and have saved lives by matching kidney patients with donor organs. As if by magic these invisible, mathematical procedures give us fast, accurate answers to a range of complex problems."

Lecture 1

Our first lecture was about the important and powerful technique of Lagrange multipliers, which are used to address problems of optimization under constraints. Additional reading can be found in S. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press (2004), chapters 1 and 5.

 One person asked why, in a line of the proof of Theorem 1.3, we can use $\inf_{c\in \mathbb{R}^m} \inf_{x\in X(c)} =\inf_{x\in X}$. Another class member provided the correct answer: that every $x\in X$ satisfies $h(x)=c$ for some $c$. 

Subsequent to the lecture I corrected the numbering of Theorem 1.3 on page 3. I will sometimes make small changes to the notes after a lecture.

As we begin, some of you may be wondering: what is Operational Research? Here are some links that may help to explain.

PROFESSIONAL SOCIETIES
INFORMS is US-based,society but has members throughout the world and organizes many conferences. They have sections in theoretical fields such as Applied Probability, and more applied ones such as Transportation Science & Logistics. On their web site they try answer: What is Operations Research?

They say, "Operations Research (O.R.), or operational research in the U.K, is a discipline that deals with the application of advanced analytical methods to help make better decisions. The terms management science and analytics are sometimes used as synonyms for operations research. Employing techniques from other mathematical sciences, such as mathematical modeling, statistical analysis, and mathematical optimization, operations research arrives at optimal or near-optimal solutions to complex decision-making problems."

The UK society is the the Operational Research Society: https://www.theorsociety.com/

RESEARCH FUNDING
Here is a graphic of research areas in the Mathematical Sciences supported by EPSRC

Total theme funding, £210.2 million (4.66% of whole portfolio). There are 350 grants in the Mathematical Sciences theme. Mathematical Aspects of Operational Research presently has 21 grants, totalling £8m and is represented by the circle at the bottom of the picture.

RESEARCH PUBLICATION
Mathematics of Operations Research  is a leading journal. If you look at the titles of some articles this will show that there is some quite deep mathematics being pursued.

Mathematics of Operations Research (MOR) publishes excellent foundational articles having significant mathematical contents and relevance to operations research and management science.

Course starts Friday, 9 October

This is the first post on the blog page for my MMath/MASt course, starting 9 October 2015.

Lectures will be in room MR14 between 11.05 and 11.55.

There will be 3 examples classes, on Tuesday November 3: 16:00-18:00, Tuesday December 1: 16:00-18:00 and Tuesday January 19: 16:00-18:00.