Linear and Mixed Integer Programming
Home

• \(x\) is feasible if it satisfies all constraints.
• Feasible region is the set of all feasible points.
• \(x\) is optimal if it satisfies all constraints and \(f(x) \le f(y)\) for any other feasible solution \(y\).
• Goal: find an optimal solution.

There are 3 possibilities –

1. LP has an optimal solution.
2. LP is infeasible – i.e. we have too many constraints. For example, \[\min x\] subject to
   • \(x\le 1\)
   • \(x\ge 2\)
   • \(x\ge 0\)
3. LP is unbounded – i.e. we have too few constraints. For example, \[\max x\] subject to \(x\ge 0\).

CPLEX, COIN-OR, FICO Xpress, GLPK, Gurobi, \(\ldots\)

Maximize \(c^\top x\) subject to

• \(Ax\le b\)
• \(x\ge 0\)

Here, \(c\) is the vector of coefficients in the objective. \(A\) is the matrix of constraint coefficients. \(b\) is a vector of constants.

• Affine constraints
• Linear objective function
• Can be solved efficiently
• The feasible region is always a polyhedron
• The optimal solution (if it exists) is always a vertex of the polyhedron.

• The optimal solution must occur at a vertex of the polyhedron created by all the constraints.
• Start at a vertex. Move to neighboring vertex with lower function value.
• This movement can be done in \(\mathcal{O}(mn)\) time, where \(m\) is the number of constraints and \(n\) is the number of vertices of the polyhedron (or perhaps it is the dimension of \(x\)? I am not really sure).
• In theory, the number of vertices in the polyhedron can depend exponentially on \(m\).
• But in practice, the Simplex method is very efficient and tractable.

The interior point algorithm.

• Runs in polynomial time.
• Sometimes faster than the simplex method.

Primal	Dual
\(\max_x c^\top x\qquad\)	\(\min_\lambda b^\top \lambda\)
subject to	subject to
\(Ax \le b\)	\(\lambda^\top A \ge c\)
\(x\ge 0\)	\(\lambda \ge 0\)

Let \(x\) be a feasible solution to primal. Let \(\lambda\) be a feasible solution to dual. Then, \[c^\top x \le b^\top \lambda\]

Proof

\begin{align*} \lambda^\top A &\ge c \\ (\lambda^\top A)x &\ge c^\top x, \text{ since }x\ge 0 \\ \lambda^\top (Ax) &\ge c^\top x \\ \lambda^\top b &\ge c^\top x, \text{ since }b\ge Ax \end{align*}

If either the primal or the dual has an optimal solution, then both problems do, and moreover, the objective values are equal, i.e. \[c^\top x = b^\top \lambda.\]

1. If objectives of primal and dual solutions are close in value, then solution is close to optimal.
2. If objectives are equal, then solutions are optimal.
3. Simplex and interior point methods are guaranteed to produce optimal solutions to both primal and dual.
4. Intermediate solutions from interior point methods are always feasible for both primal and dual in each iteration.
5. Intermediate solutions from simplex method might not be feasible for dual solution in each iteration (until optimal solution is found in the last iteration).

• Linear programs have both strong and weak duality.
• Many convex optimization problems have strong duality.
• Integer linear programs have weak duality.

• Affine constraints
• Linear objective functions
• Restriction that some/all variables are in \(\mathbb{Z}\)
• NP-Hard in general
• Current algorithms require EXP time in worst case.
• In practice, however, it is tractable.
• Yes/No problems can be modeled as binary variables in the set \(\{0, 1\}\).

Suppose \(x,y \in \{0, 1\}\) are binary variables.

• \(x\le y\) enforces \(x\rightarrow y\).
• \((1-x)\) is the same as \(\neg x\).
• Therefore, \(1-x \le y\) enforces \(\neg x \rightarrow y\). Said differently, \(x+y\ge 1\) enforces \(x\vee y\).

Given an Integer Program (IP), if we relax the integrality conditions on the variables, we get a Linear Program (LP).

Here are some key facts about such a relaxation –

1. For minimization problem, the optimal value of LP-relaxation of IP serves as a lower bound of IP.
2. For maximization problem, optimal value of LP-relaxation of IP serves as an upper bound of IP.
3. If optimal solution of LP-relaxation is integral, then it is also the optimal solution to the IP.

Method 1: Branching on a variable \(x\)

Divide feasible region into two smaller regions \(x \le \lfloor v \rfloor\) and \(x\ge \lceil v \rceil\), where \(v\) is the optimal decimal solution to \(x\). This is part of a popular method for MILP called "branch and bound method".

Method 2: Cut generation

Add a new constraint that cuts away some of the floating-point solutions while not removing the integer solutions.

In practice, both methods are used in conjunction.

If polyhedron associated with formulation \(A\) strictly contains the polyhedron associated with formulation \(B\), then we say that formulation \(A\) is stronger and \(B\) is weaker.

• Strong formulations have constraints close to the integral points in the feasible region, i.e. they have no gaps between integer points and constraints.
• Strong formulations have less possibility of yielding floating-point solutions and are more likely to yield integer solutions.
• Strong formulations require less branching and cut-generation.
• Simplex method produces optimal solutions for strong formulations.

Trade-off: However, strengthening a formulation can require us to introduce lots of new constraints, which can slow down the solver. See 2.6.

In practice, aim for maximizing the strength of the formulation.

The convex hull of integral solutions is the strongest possible formulation of an LP. However, in practice, the convex hull is hard to find.

The classic example to keep in mind is Traveling Salesman Problem.

Here are the steps –

1. Start with a weak formulation
2. Solve IP without subtour elimination (in case of TSP, this is when smaller cycles occur, which we wish to eliminate).
3. Check for subtours in resulting solution.
4. Add subtour elimination constraint.
5. Repeat until no subtours appear.
6. This solution is optimal.

Separation problem is the problem of identifying a constraint that has been violated.

If constraint generation is applied to integer solutions only, then we can identify violated constraints efficiently.

Tabu search

Make a list of recent solutions already checked in the neighborhood of current solutions.

Simulated annealing

Pick a neighborhood solution based on a probability \(e^{-\Delta/T}\), where \(T\) is a steadily decreasing temperature.