# TDA206 - Discrete Optimisation

Lecture notes - Lecture 3

## 1 About these notes

These notes were not written in class as I was away on vacation during this lecture, therefore it is instead based on last year's lecture notes for the second week. These notes will mainly be paraphrases of those notes. That's why there might be some overlap between these notes and last lecture's notes.

## 2 Linear Programming (cont.)

Linear programming is a special case of convex optimization that was one of the first optimization problems to be carefully studied and solved as it is tightly bound to linear algebra. Much of the advancements in other areas of optimization theory were inspired by Linear programming. In the same way that affine functions and half-spaces are the building blocks of convex functions and convex sets, linear programming is the foundation of all convex optimization problems.

Linear programming is interesting in this course because it is used
heavily in the theory of discrete optimization. We can formulate
many interesting problems as *Integer Linear Programs (ILP)* which
are similar to LP's but have discrete variable space instead of
continuous. However, before we dive into ILP's we will focus a bit
more on LP's and possibly recap a bit from last lecture's notes.

### 2.1 Definition 1

An optimization problem is linear if:

- The variable domain is for som .
- The cost function and the constraint functions and are all affine functions.

It is popular to write an LP as

### 2.2 Matrix definition

This could easily be written using matrices, like this:

Now the optimization can be written as

### 2.3 Alternative forms of expressing LPs

Often we don't need all the matrices **A**, **b**, **c**, **D** and **e** to
express an LP. There are two common forms to express an LP:
*standard form* (or *canonical form*) and the *augmented form*.

Standard form:

Augmented form:

To turn a general form of LP into one of these forms, the following modifications are straightforward:

- Minimization of can be turned into maximization of .
- Lower bounds can be turned into .
- Equality constraints can be turned into two inequality constraints and
- Inequalities can
be turned into equalities by introducing a new
*slack variable*(hence the term "augmented" form), and replacing the constraint by . - Unconstrained variables can be replaced by .

### 2.4 Primal and dual LPs

Given a *primal problem P*

The *dual problem D* is defined as

### 2.5 Weak duality in LP

By minimizing the objective function for *D*
() we can obtain an upper bound
for the maximal solution of *P*.

**Theorem** (Weak duality in LP).

*If there exists a feasible in P, and a feasible in D,
then .*

*Proof.* If we left-multiply the constraint in *P* () with a non-negative vector we will
get the inequality . Doing the same thing for the
constraint in *D* with another non-negative vector
gives us and transposing that leaves us with
Assuming that the feasible regions of *P* and *D* are note empty we
can pick a and an to
obtain the inequality .

The difference between two objectives is called the *duality
gap*. There is for linear programs an even stronger theorem which
we are not going to prove.

### 2.6 Strong duality of LP

**Theorem** (Strong duality of LP).

*If P has a feasible optimal solution , then D has an optimal feasible solution ,
and .*
*If P is unbounded, then D is infeasible. If D is unbounded, then P is infeasible. If either one is infeasible,
the other is infeasible or unbounded.*

In other words, the duality gap in LP is zero, except when both are infeasible, then it is infinite. Strong duality tells us that we can solve a maximization problem by solving its dual and vice versa. We can quickly decide if a problem in unbounded. Also, in LP, the dual of the dual is the primal.

### 2.7 Complementary slackness

There is another way to determine whether a solution to a promal is
optimal, using a property called *complementary
slackness*. Consider the first equality in the strong duality
theorem, . This
can be written as follows:

Since is feasible, we know that and therefore for all . On the other hand, we know that for all since is also feasible. Since

and none of its terms can be positive, we have

because there can be no positive terms to cancel out any negative ones. This menas that in order to satisfy the equation above, for every , at least one of and must be 0. means that is satisfied with equality.

### 2.8 Active constraints, constraint with slack and complementary slackness

**Definition** *An inequality constraint is said to be* binding *or* active *if for some given*
*it is satisfied with equality, i.e
.*
*It is said to have* slack /if it is not binding.

An analogous argument can be made for . This yields the following important result:

**Theorem** (Complementary slackness).

*If optimal solutions exist for the primal
and dual LPs P and D, then the following holds:*

*If the i-th primal constraint has slack, then the i-th dual variable is zero.**If the j-th dual constraint has slack, then the j-th primal variable is zero*.*If the i-th dual variable is positive, then the i-th primal constraint is*binding.*If the j-th primal variable is positive, then the j-th dual constraint is*binding.

The following might be useful for visualizing the correspondence of variables in the primal-dual relation: