Linear and Integer Programming (CPS 590.01), Fall 2012


image taken from http://users.informatik.uni-halle.de/~jopsi/drand04/linear_programming.gif
WF 10:05AM-11:20AM, North Building 306.
Instructor: Vincent Conitzer. Office hours: immediately after class and/or by appointment.

Topics: Linear programming: applications, simplex method, duality theory, advanced techniques. Integer programming: applications, modeling, branch-and-bound, polyhedral theory, valid inequalities, advanced techniques.

Prerequisites: Linear algebra; probability; mathematical maturity (including ability to write a formal proof); basic computer science background or instructor's permission. Feel free to approach the instructor if you have questions.

Summary:
In a linear program, we are given constraints of the form a_{i1}*x_1 + a_{i2}*x_2 + ... + a_{in}*x_n <= b_i, and we are asked to find values of the x_j that maximize an objective c_1*x_1 + c_2*x_2 + ... + c_n*x_n, subject to the constraints. In an integer (linear) program, the x_j must take integer values. In a mixed integer (linear) program, only some of the x_j must take integer values.

Surprisingly many optimization problems can be naturally modeled as linear or integer programs, and for this reason these techniques are increasingly used across many areas of computer science. For example, they tend to be particularly useful for problems related to economics that are of increasing interest to computer scientists. In this course we will practice modeling optimization problems as linear or integer programs, cover some of the underlying theory and practice drawing implications from this theory to our application problems, and cover algorithms and packages for solving linear and integer programs. There will be a significant project component.

Relevance to computer science theory and AI:
In spite of the strong algorithmic component of linear and integer programming, for historical reasons, much of the development of the techniques for these problems has taken place outside the computer science community. Because of this, computer scientists in general are perhaps less aware of them than they should be. Computer science theorists tend to be familiar at least with the techniques that allow for proving polynomial-time solvability, but are perhaps less interested in the (worst-case exponential-time) techniques for solving integer programs to optimality. Among AI researchers, the familiarity is perhaps lower (with the exception of some subareas), even though they are generally not averse to algorithms that require exponential time in the worst case if they "usually" perform well. Indeed, many of the algorithms for integer programming are very similar to AI search algorithms.

Nevertheless, computer scientists (both in theory and AI) are increasingly looking at problems where these methods can be fruitfully applied. For example, the use of probabilities is becoming more common, which are continuous quantities that are naturally expressed in linear and integer programs. Moreover, both in theory and AI, there is increasing interest in problems from economics and game theory, which often lend themselves especially well to formulation as a linear or integer program.

Readings
There will be self-contained lecture notes for this course. Here are some (strictly optional) additional resources:
A course at Harvard.
Applied Mathematical Programming, a book freely available online.
Convex Optimization, a book freely available online.
Understanding and Using Linear Programming, can be read online.

Grading
Participation: 10%
Homework: 20%
Midterm: 20%
Project: 50%
Bonus points: any mistakes/errors/typos that you (are the first to) find in my lecture notes (please send me e-mail with subject header "Mistake in notes").

You may discuss assignments with at most one other person in the class. Each person must do her or his own writeup and write his or her own code. This also means that you may not copy any (partial) solutions or code fragments from each other (even within your team of two). In your team of two, you may present things to each other on (say) a whiteboard, but the other person should not simply be copying things over. (Of course, you may also work by yourself if you prefer. Also note that these rules only apply to the assignments, not the project.) You should acknowledge everyone you worked with, as well as all other sources, on the writeup. (So, I expect that if A acknowledges B, then B acknowledges A, and presumably neither of them acknowledges anyone else; though, if you find some reason to acknowledge someone else -- e.g., you went to another lecture that happened to have something significantly useful for this assignment -- you are encouraged to acknowledge this.) Of course, you may not look for solutions to similar homework assignments from past versions of the course. I have some tricks for catching this. (To avoid triggering some of these tricks, please be very careful not to somehow accidentally look at a similar assignment from a past version of the course.) Assignments are always due immediately at the beginning of class.

Projects
As you can see from the grading, the project is an important part of this course. You may work on it alone or in a team (please check with Vince first if you want to have a team of more than 3 people). I imagine that most projects will consist of using linear/integer programming in some application domain, perhaps in your own research area. Because of this, we will start discussing some example applications very early in the course, so that you can start thinking about how you might apply these techniques to something that you care about. We will have some checkpoints (e.g., project proposal) during the course, but feel free to discuss possible project ideas with Vince earlier.

The goal of the project is to try to do something novel, rather than merely a survey of existing work. Projects may be theoretical, experimental (based on simulations), experimental (based on real-world data), a useful software artifact, or any combination thereof. The only real constraint is that it has something to do with linear/integer programming. Talk to Vince if you are not sure about whether something is an appropriate project. The final product is a writeup (in the form of a research paper) and a class presentation (all team members must participate in the presentation). Some projects may well lead to publishable papers (perhaps with some additional work).

In your project proposal, you should explain the topic of your project, what types of results you hope to obtain, and what some of the technical issues are that you will need to address. If necessary, Vince can help with finding topics. Something related to your own research is definitely OK as long as it also has something to do with linear/integer programming. An intermediate project progress report is also required. This report should explain what results you have obtained already, what (if any) difficulties you encountered, and what you plan to do to complete your project. Ideally, at this point, you should already have some good results, so that you can spend the rest of your time on answering questions generated by your results, as well as preparing your writeup and presentation.

Schedule
We will be flexible with the schedule. One set of lecture notes will not necessarily take one lecture to finish.

Date	Topic	Materials
Aug. 29	Introduction. Examples of linear and integer programs. Solution by graphical inspection. Linear programs in abstract form.	Lecture notes 1. "The algorithms that runs the world" article.
Aug. 31 - Sep. 7	Applications. Maximum flow. Combinatorial (reverse) auctions. Zero-sum games. Markov decision processes. (Kemeny) rank aggregation. Sudoku.	Lecture notes 2.
Sep. 12	Using the GNU Linear Programming Kit and its modeling language.	Lecture notes 3. Also from class: sudoku.mod, wdp.mod. GNU Linear Programming Kit (GLPK) (including documentation). Possibly useful notes from IBM. Homework 1.
Sep. 14	Duality. Weak duality, strong duality, complementary slackness.	Lecture notes 4.
Sep. 19, 21	Duality in applications.	Lecture notes 5.
Sep. 26	Guest lecture: Josh Letchford. Linear and integer programming in game theory.	Slides: pptx, pdf.
Sep. 28, Oct. 3, 5	The simplex algorithm.	Lecture notes 6.
Oct. 10	Homework review.
Oct. 12	Guest lecture: Dima Korzhyk. Commitment to correlated strategies.	Slides: pptx, pdf.
Oct. 17, 19	Network flow problems.	Lecture notes 7. Homework 2.
Oct. 24	MIDTERM.
Oct. 26	Guest lecture: Angelina Vidali. (Automated) mechanism design.	Mechanism design slides, automated mechanism design slides. Automated mechanism design chapter.
Oct. 31, Nov. 2	Constraint and column generation. The cutting stock problem.	Lecture notes 8.
Nov. 7, 14	An illustrative example: the core and network flows.	Lecture notes 9.
Nov. 9	Homework review.
Nov. 16	Branch and bound.	Lecture notes 10.
Nov. 16	Valid inequalities/cutting planes.	Lecture notes 11.
Nov. 26	Project presentations. Pablo, Yuqian, Branka.
Nov. 28	Project presentations. Animesh, Garrett, Ergys+Mayuresh.
Nov. 30	Project presentations. Marisabel, Michael, Seyed.

---