# Discrete Optimization

https://www.coursera.org/learn/discrete-optimization

## Knapsack

• Relaxed problem
• Branch and bound
• Depth/Breast/Best First Search
• Limited Discrepancy Search

following the heuristic means branching left

explore the search space in increasing order of mistakes

• Algorithm
• Discard items that don’t fit
• Multiply each value by something so that values are small. Max scaled value = N = 100 * n (n is number of items)

The value is at least 1-1/c OPT for N = c*n

• Round values down to integers (floor)
• Dynamic program for the scaled and rounded problem

## Constraint Programming

• Global Constraint
• alldifferent(x1,…,xn)
• table constraint

only several combination of values are admissibles

• Break variable symmetries

Impose an ordering on the variables

• Redundant constraints

Do not exclude any solution by reduce the search space and boost the propagation of other constraints

• Other ideas
• Choose value then choose variable
• Domain splitting
• Randomization and restarts

Strategies

• Minimize violations

choose a decision variable that appear in the most violations and assign it to a value that minimizes its violations

• SWAP

Instead of reassigning values, swap the values of variables

The traveling tournament problem (TTP) / Warehouse location / Car Sequencing

The traveling tournament problem (TTP)

• swap homes
• swap rounds
• swap teams
• partial swap rounds
• partial swap teams
• K-OPT

The traveling salesman problem (TSP)

• Escape local minima
• Different start point
• Metropolis algorithm

accept a move if it improves the objective value or, in case it does not, with some probability which depends on how “bad” the move is

exp(-delta/t) where t is the temperature

• Simulated Annealing

Use Metropolis algorithm but adjust the temperature dynamically

t *= alpha

• Generate initial solution
• Initialize t
• loop
• Local Search
• Update(Maybe reheat)
• Tabu

maintain the sequence of nodes already visited

select the best configurations that is not tabu

• Short-term memory

only keep a small suffix of visited nodes

may increase or decrease the size of the list dynamically

• decrease when the selected node degrades the objective
• increase when the selected node improves the objective
• swap

when tabu[i,j] > iteration, it’s a tabu

when apply a move tabu[i,j] += L

we can use (i, j, f1, f2) to denote that i and j have been swapped from an objective value f1 to f2

• if the solution is good enough, it’s not a tabu
• Restart
• Reheat
• Others
• Intensification

• Diversification

when the search is not producing improvement, diversify the current state, e.g., randomly change the values of some variables

• Strategic oscillation

change the percentage of time spent in the feasible and infeasible regions

• Variable neighborhood search
• Guided local search
• Ant-colony optimization
• Hybrid evolutionary algorithms
• Scatter search
• Select neighbor
• Select the first/best neighbor/improvement
• Select the first legal
• Multi-stage selection
• select the variable with the most violations and select the value with the fewest violation
• select the variable with some violations and select the value with the fewest violation
• Select at random

## Linear Programming

where $b_m\geq 0$

The solution space is convex set and the optimal solution is at a vertex.

### Simplex Algorithm

1. A basic feasible solution (BFS) is like:

If we take $x_i=0$ for $i=m+1,\cdots,n$, then $x_i=b_i$ for $i=1,\cdots,m$.

Here $x_i$ for $i=1:m$ are basic variables and $x_i$ for $i=m+1:n$ are non basic variables.

2. To move from a BFS to a better one,

• Select an entering variable $x_e$ at right-hand side with $c_e<0$
• Select a leaving variable $x_l$ at left-hand side:

• Perform Gaussian elimination to eliminate basic variables

If $c_e<0$ and all $a_{ie}\geq 0$, then we can increase $x_e$ arbitrarily to decrease the objective arbitrarily.

If $b_i=0$, make $x_i$ leave do not change the objective.

To assure the termination, we can select always the first possible entering variable.

3. To detect whether a BFS is optimal

If after having eliminated all the basic variables, the objective function is of the form

with $\forall i, ~c_i\geq 0$

4. To find the first BFS, we can introduce artificial variables:

It’s a BFS with $y_j$ at left-hand side.

In order to remove $y_j$, we consider the following problem

#### Matrix Representation

 $c_1$ … $c_n$ $-z$ $a_{11}$ … $a_{1n}$ $b_1$ … … … … $a_{i1}$ … $a_{in}$ $b_i$ … … … … $a_{m1}$ … $a_{mn}$ $b_m$

#### Duality

• Primal

• Dual

For this problem, if the primal has an optimal solution, the dual has an optimal solution with the same cost.

##### Exemple

It can be interpreted as:

The dual problem use the combination of constraints to find a lower bound of the primal problem.

Why we use the dual problem ?

If we have an optimal solution for the primal problem and we want to add a new constraint which makes the solution infeasible, but the dual is still feasible (we only need to add a dual varaible). Then we can solve the dual until the optimality and the solution becomes feasible for primal.

Moreover, the primal/dual problem use the same matrix table to solve the problem.

## Duality

Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

### Primal problem

We consider the following primal problem:

### Dual problem

We can rewrite the primal problem as an unconstrainted problem

where

These functions $I_-,I_0$ are used to express our displeasure associated with the constraint function value $f_i(x)$.

And we can replace $I_-(u)$ with $\lambda_i u$ where $\lambda_i\geq 0$ and $I_0(u)$ with $v_i u$ where $v_i\in\mathbb{R}$.

Since $\lambda_i u\leq I_-(u)$ and $v_i u \leq I_0(u)$, we have

We define the Lagrange dual function $g(\lambda,v)$ as

and the dual problem:

This dual problem is a convex optimization because the objectif is the pointwise infimum of a family of affine functions and so it’s concave. This is the case whether or not the primal problem is convex.

### Weak/Strong duality

Moreover, we can note that

So we can express the optimal value of the primal problem as

and by the definition of the dual problem, we can also express the optimal value of the dual problem as

So we have the weak duality:

because

so, for each $x$,

Therefore, we can do the infimum over $x$:

If

then we say that strong duality holds.

### KKT Optimality Conditions

Karush-Kuhn-Tucker conditions:

For any optimization problem for which strong duality obtains, any pair of primal and dual optimal points must satisfy the KKT conditions (necessary). When the primal problem is convex ($f_i$ are convex and $h_i$ are affine), the KKT conditions are also sufficient for the points to be primal and dual optimal.

### Interpretation

Lagrange duality has an interesting economic interpretation.

Suppose the variable $x$ denotes how an enterprise operates and $f_0(x)$ denotes the cost. Each constraint $f_i(x)\leq 0$ represents a limit on resources (e.g., warehouse space, labor). The operating condition that minimizes cost while respecting the limits can be found by solving the problem:

The resulting optimal cost is $p^*$.

If now the limits can be violated by paying an additional cost which is linear in the amount of violation: $\lambda_if_i$. The coeffcient $\lambda_i$ has the interpretation of the price for violating $f_i(x)\leq 0$. We assume $\lambda_i \geq 0$, i.e. the firm must pay for violations and it receives income if a constraint is not tight.

So the total cost to the firm, for operating condition $x$, and constraint prices $\lambda_i$, is:

The firm will obviously operate so as to minimize its total cost $L(x,\lambda)$, which yields a cost $g(\lambda):=\inf\limits_x L(x,\lambda)$. The optimal dual value, $d^*=\sup\limits_{\lambda\geq 0}g(\lambda)$, is the optimal cost to the enterprise under the least favorable set of prices.

$d^*\leq p^*$ since in the second scenario some income can be derived from the constraints that are not tight. And if strong duality holds, the $\lambda^*$ is a set of prices for which there is no advantage to the firm in being allowed to pay for constraint violations or receive payments for nontight constraints. $\lambda^*$ is sometimes called a set of shadow prices for the primal problem.

### Slater’s condition

For the following problem:

If there exists an $x\in\text{relint}D$ with

where $D=\bigcap\limits_{i=1}^m\text{dom}~f_i$ and $f_i(x),i=1:k$ are affine,

then the strong duality holds.

## Mixed Integer Programming

Some variables have to be integers

Integer variables are typically 0/1 varaibles.

### Branch and bound

Solve the linear relaxation

• If the linear relaxation is worse than the best solution found so far

Prune this node

• Else if the linear relaxation is integral

We find a feasible solution and update the best feasible solution if appropriate

• Otherwise, the solution is infeasible

• Find an integer variable $x$ that has a fractional value $f$

• Crearte two subproblems $x\leq \lfloor f\rfloor$ and $x\geq \lceil f\rceil$

• Repeat the algorithm on the subproblems

### Big M Transformation

A constraint that two integers $x,y$ are different is $x\neq y$ which is equivalent to

Since the disjunction is not allowed in a MIP model, we can introduce a 0/1 variable $b$ and a large number $M$

But the linear relaxation will choose $b=0.5$

### Gomory Cut

The idea is to add a linear constraint that:

• is valid: it doesn’t remove any feasible solution
• helps: it cuts the optimal solution of the linear relaxation

For example, we have the following constraint and $b_1$ is fractional:

Since $\sum\limits_{j=m+1}\lfloor a_{1j}\rfloor x_j \leq \sum\limits_{j=m+1}a_{1j}x_j$

Since the left hand-side is an integer

So

The cut is actually to add a variable $s$ which should be positive

#### Algorithm:

• Solve the linear relaxation
• Choose a row i whose constant is fractional and add the Gomory cut
• Apply the dual simplex to obtain feasibility
• Iterate until the solution is integral or there is no feasible solution

### Polyhedral Cuts

Cuts that represent the facets of the convex hull of the integer solution

If we have all the cuts, we could use linear programming to solve the problem.

### Cover Cuts

Consider the following constraint:

A set $C\subset\{1:n\}$ is a cover if

and a cover is minimal if any subset is not a cover.

If $C$ is a cover, then the solution need to satisfie

which is equivalent to

Given a solution, we would like to know whether there exists a cover cut that cut the solution. Which means is there a cover set $C$ that the solution violate the constraint:

To answer this question, we only need to solve the following problem:

If the minimum value is lower than 1 then we have a cut, otherwise the cut doesn’t exist.

By replacing $z_j$ by $1-y_j$, it’s a Knapsack problem.

### Column Generation

Column Generation for Cutting Stock