# Linear and Integer Programming

From IFORS Education Resources

**By: Vincent Conitzer**

**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 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 be integers. In a mixed integer (linear) program, only some of the x_j must be integers.

Surprisingly many optimization problems can be modeled as linear or integer programs. In this course, we will study how to model problems as linear or integer programs, and study basic methods (algorithms) for solving them.

**Link to material:** http://www.cs.duke.edu/courses/spring08/cps296.2/