Optimization Engineering

Dr. LIPIKA PANIGRAHI

Associate professor in mathematics

Gandhi Institute foe Education and Technology

​

Outlines

• Linear programming
• Transportation and Assignment problem
• Integer problem
• Mixed Integer problem
• Queuing theory

LINEAR PROGRAMMING�Segment 1

Definitions

Feasibility and optimality

Linear programs in standard form

“Economical” interpretation/application

LP in two dimensions – geometric interpretation

Linear programs in slack form

Linear Programming

Optimize (maximize or minimize) �a linear objective function subject to a set �of linear constraints (equalities and inequalities)

A problem of this form is called a linear program.

LP:

Feasibility and optimality

(Assuming the LP is a maximization program.)

An LP is feasible if it has a feasible solution.

An LP has an optimal solution iff it is feasible and bounded.

Importance of Linear Programming

Linear Programming has a lot of applications.

LP can be solved efficiently both in theory and in practice.

Many problems, including some of the problems �considered in this course, are LP problems.

Many software packages can solve LP problems.

We shall learn the simplex algorithm, and use it �to prove the duality theorem for linear programming

The simplex algorithm behaves very well in practice. But, �there are pathological examples on which it is not polynomial.

There are other, more complicated, LP algorithms that �run in polynomial time. (Ellipsoid, interior-point, etc.)

LPs in standard form

All variables are constrained to be non-negative.�(Very special linear inequalities.)

LPs in standard form

transpose

“Economic” application

How many units of each product should �we produce to maximize our profit?

Converting an LP to standard form

Every LP can be easily converted to standard form.

LP in two dimensions

Figure 29.2 from CLRS

Each constraint �defines a half-plane.

The intersection of all these �half-planes is a polygon,�called the feasibility polygon.

The objective function �specifies a direction.

The goal is to find the furthest feasible point in this direction, �i.e., the point with the largest inner-product with the direction.

LP in two dimensions

Figure 29.2 from CLRS

Each constraint defines a half-space.

The intersection of the constraints is the feasibility polyhedron.

The extreme points of the polyhedron are called vertices.

The finite intersection of half-spaces is a polyhedron.

There is always an optimal solution which is a vertex.

Equational Form

Standard form 🡪 Slack form

The resulting LP is said to be in slack form.

All constraints, except the non-neg constraints are equalities.

Slack form

Standard form

Standard form 🡪 Slack form

For those interested,�this is the corresponding�equational form:�(We will not use �it explicitly.)

Standard form

Slack form

END OF �SEGMENT 1

LINEAR PROGRAMMING�Segment 2

The simplex algorithm by example

The simplex algorithm by example

max

s.t.

max

s.t.

Start with an LP in standard form:

Convert it into slack form:

Basic and non-basic variables

max

s.t.

In a basic solution, all non-basic variables have value 0.

Pivoting step (1)

max

s.t.

Pivoting step (2)

max

s.t.

For brevity, from now on we do not�explicitly show the non-negativity constraints.

It is important to remember that they are still there!

Pivoting step (3)

max

s.t.

Pivoting step (4)

max

s.t.

Pivoting step (5)

max

s.t.

An equivalent slack form

max

s.t.

The new form is completely equivalent to the previous form.

The objective function is the same.

We have a new basic feasible solution of value 27.

Another pivoting step

max

s.t.

We do row operations to get a new equivalent form.

Another equivalent slack form

max

s.t.

Final slack form

max

s.t.

It achieves a value of 28.

END OF �SEGMENT 2

LINEAR PROGRAMMING�Segment 3

The simplex algorithm

The simplex algorithm�[Dantzig (1947)]

Start with a problem in standard form.

Try to find an equivalent slack form that �yields a basic feasible solution (bfs).

If no such slack form is found, the problem is infeasible.

If all coefficients in the objective function are �non-positive, then the current bfs is optimal.

The simplex algorithm – more details

If no initial bfs can be found, the problem is infeasible,

If there are several non-basic variables with positive coefficients (also called modified costs), we need to choose one of them.�This is done using a pivoting rule.

If there are no degenerate steps, then the objective value �strictly increases, and the algorithm must eventually terminate.

Basic and non-basic variables

The slack form, also known as the simplex tableau:

The basic solution corresponding to the slack form is:

If it is feasible, it is called a basic feasible solution (bfs).

If the set is empty, the problem is unbounded.

A pivoting step – updating the table (1)

A pivoting step – updating the table (2)

A pivoting step – updating the table (3)

Finally, we update the objective function:

All simple algebraic operations.

END OF �SEGMENT 2

THE SIMPLEX ALGORITHM�Segment 4

Pseudocode

Termination

Degeneracy

Cycling

Pivoting rules

Complexity

The simplex algorithm – pseudocode

A pivoting step

Convert the slack form:

into the slack form:

Termination

There may, however, be degenerate iterations in �which the objective function stays the same.

If there are no degenerate iterations, then the objective �function strictly increases we can never visit a bfs again.

Thus, if there are no degenerate iterations, the simplex� algorithm terminates after a finite number of iterations.

Note, however, that the upper bound on the �number of iterations is not polynomial.

Degeneracy

Example of degeneracy:

degenerate step

Degeneracy occurs a lot when solving combinatorial problems.

Cycling

In the example given, the degenerate step �was followed by a non-degenerate step.

Can we have several consecutive degenerate steps?

Can the degenerate steps form a cycle,�i.e., return to a previously visited bfs?

Unfortunately, cycling can happen, if we do not �carefully choose the entering and leaving variables.

(The smallest cycling example known is on an LP �with 7 variables that gives a cycle of length 6.)

Avoiding cycles

A crude way of avoiding cycles is to slightly perturb �the linear program. Cycles are unlikely to happen.

But, this slightly changes the optimal solution.�(Can be fixed by doing the perturbations ‘symbolically’.)

A more satisfying to solution is to use Bland’s rule.

Bland’s rule: (Use the smallest index)

Theorem: The simplex algorithm with Bland’s rule cannot cycle.

(We do not prove the theorem in this course.)

Pivoting rules

However, rhe pivoting rule can have a significant effect �on the efficiency of the simplex algorithm.

Note: We can revert to Bland’s rule if we see �that we are about to perform a degenerate step.

If cycles are avoided, the simplex algorithm returns �an optimal solution no matter which pivoting rule is used.

Common pivoting rules

Unfortunately, the simplex algorithm with these rules, �and many other rules, is not polynomial in the worst case.

It is a major open problem whether there is a pivoting �rule that makes the simplex algorithm polynomial.

END OF �SEGMENT 4

THE SIMPLEX ALGORITHM�Segment 5

Finding an initial bfs

The auxiliary LP

Existence of optimal basic solutions

Checking feasibility and �finding an initial basic feasible solution

Standard form

Slack form

We need to check whether the LP is feasible, and if so, �find a bfs to start the simplex algorithm from.

Auxiliary LP

Original LP

Auxiliary LP

To check feasibility, we introduce an auxiliary LP.

Running simplex on the Auxiliary LP

To solve the auxiliary LP we use the simplex algorithm.

We first transform it into slack form.

But, don’t we have exactly the same problem?

But, we can easily manipulate the slack form to get a bfs.

Finding a bfs of the auxiliary LP

The new basic solution is feasible!

Solving the auxiliary LP

We found a bfs of the auxiliary LP,�i.e., a slack form that defines a bfs.

We can thus use the simplex algorithm to solve the auxiliary LP.

We do not present pseudo-code.

The auxiliary LP is bounded, as�the value of the objective function is at most 0.

Optimal basic solutions

Corollaries of the correctness of the simplex algorithm:

Other implications of the simplex algorithm will be discussed �in the next segment when we consider LP duality.

(The theorems say that there is always an optimal solution �which is a vertex (extreme point) of the feasibility polyhedron.)

END OF �SEGMENT 5

LINEAR PROGRAMMING�Segment 6

LP duality

“Deriving” the dual program.

Weak duality

Defining the dual program.

LP duality theorem

LP duality

primal

To every LP in standard form we define a dual:

dual

Maximization becomes minimization.

LP duality theorem

Theorem: If the primal and dual linear programs�are both feasible, then their optimal values are equal.

primal

dual

Deriving the dual

We want to get an upper bound on the optimal value of the primal.

The theorem, which needs a proof, says that the best bound is tight!

primal

Weak duality

In the previous slide we proved the following weaker �version of the duality theorem known as weak duality:

Here is the same proof written in matrix notation:

END OF �SEGMENT 6

LINEAR PROGRAMMING�Segment 7

LP duality

Economical interpretation of the dual

Interpretation of the dual (1)

Recall:

primal

dual

Interpretation of the dual (2)

Primal: How do we maximize our profit?

primal

dual

Interpretation of the dual (3)

Dual: What is the minimal total worth of an offer we accept?

Instead of producing products, we try to sell the raw materials.

primal

dual

“Shadow prices”

END OF �SEGMENT 7

LINEAR PROGRAMMING�Segment 8

LP duality

Proof of the duality theorem

Lemma

Before proving the lemma we use it to prove strong duality.

Consider an initial slack form:

and the objective function of an equivalent slack form:

Then:

Reduced costs

Proof of duality theorem

We show that the simplex algorithm produces not only a �primal solution, but also a dual solution, and they both have �the same value. By weak duality, they are both optimal.

Proof of lemma

Simple calculations similar to those we saw before.

END OF �SEGMENT 8

LINEAR PROGRAMMING�Segment 9

LP duality

A “full” version of the duality theorem

Duals of LP programs that not in standard form

Frakas’ Lemma

Full LP duality theorem

(P)

(D)

(1) If (P) is feasible and bounded, then so is (D), and vice verse. �(P) and (D) have optimal values and their optimal values are equal.

(2) If (P) is feasible but unbounded, then (D) is infeasible.

(It is possible that both (P) and (D) are infeasible.)

(3) If (D) is feasible but unbounded, then (P) is infeasible.

Primal/Dual pairs

Standard form

Inequalities form

Equational form

The LP duality theorem holds for all these forms.

The dual of the dual is the primal.

Frakas’ Lemma (1902)

Proof: Consider the pair of primal dual programs:

(1) says that (P) is feasible and bounded.

(P) always bounded. (D) always feasible. By the duality theorem:

If (P) is feasible (and bounded), then (D) is bounded. Only (1) holds.

(2) says that (D) is feasible and unbounded

Dualization Recipe

(You do not need to memorize it.)

END OF �SEGMENT 9

LINEAR PROGRAMMING�Segment 10

Linear Programming�vs.�Integer Programming

“Economic” application revisited

(LP)

Can we force the variables to assume only integral values?

Integer (Linear) Programs

(IP)

The simplex algorithm does not solve IP problems.

Solving IP problems in NP-hard.

Sometimes, we can ignore the integrality constraints, solve the �resulting LP relaxation, and then round the solution, hoping �that the solution obtained is close to optimal.

This gives us an approximation algorithm.

In some “lucky” cases, the LP relaxation always has �optimal integral solutions, so we get an exact result.

IP for Maximum Independent Set

(IP)

Finding an independent set of maximum size is NP-complete.

We can easily get an IP for the MIS problem.

Thus, IP is also an NP-complete problem.

END OF �SEGMENT 10

LINEAR PROGRAMMING�Segment 11

Formulating problems as Linear Programs

Single Source Shortest Paths

Formulating problems as linear programs

A wide variety of problems can be formulated as linear programs.

We focus in this course on graph/network related problems.

We consider LP formulations of the following problems:

Shortest paths

Maximum flow in a network

Minimum cost flow

Multi-commodity flow

For Shortest Paths we saw more efficient direct algorithms.

For Maximum flow we shall see more efficient direct algorithms.

The power of LP is its versatility and robustness.

For specific problems, more efficient algorithms can be found.

Shortest Paths – reminder

Proof: Review exercise on shortest paths.

Shortest Paths as an LP problem

(LP)

Shortest Paths as an LP problem

Shortest Paths is a minimization problem.

(LP)

Why did we formulate it as a maximization LP problem?

We can get an alternative formulation of Shortest Paths as a minimization LP problem by taking the dual. (Stay tuned!)

(LP) is infeasible.

(LP) is unbounded.

Shortest Paths as a maximization problem

(LP)

Each edge is represented by a piece of rope.

The ropes of the edges incident on a vertex a tied together.

Shortest Paths as an LP problem

What did we gain from this?

(LP)

We know much more efficient algorithms �for finding shortest paths directly.

First, it is an instructive example.

Second, if we change the problem definition, our �shortest paths algorithms are likely to stop working, �while the LP approach may remain valid.

Examples, beyond the scope of this course, are Stochastic �Shortest Paths (SSPs) and Markov Decision Processes (MDPs)

END OF �SEGMENT 11

LINEAR PROGRAMMING�Segment 12

Formulating problems as Linear Programs�Network flow problems

Maximum flow

Minimum cost flow

Multicommodity flow

Network Flow

capacities

source

sink

Network Flow

capacities

source

sink

Maximum flow

Maximum Flow is an LP problem

Maximize the total net amount of flow entering the sink.�(We show later that all this flow must leave the source.)

Subject to the conservation constraints,

capacity constraints,

and non-negativity constraints.

The problem is always feasible and bounded,�so it has an optimal solution.

Maximum Flow and relatives

As Maximum Flow is an LP problem, we immediately get �fairly efficient (polynomial time) algorithms for solving it.

This demonstrates the versatility of the LP problem.

As with shortest paths, we can get even more efficient �maximum flow algorithms by studying the problem directly.

We next consider several variants of the maximum flow problem:

Using LP, we immediately get algorithms for them too.

More efficient algorithms can also be obtained for some �of these problems, but we will not do it in this course.

Minimum cost flow

Multicommodity flow

Minimum cost multicommodity flow

Maximum flow with losses

Minimum cost Flow

source

sink

Minimum cost Flow

Minimum cost Flow is an LP problem

If the problem is feasible, then it is bounded �and has an optimal solution.

Minimum cost Flow �with general supplies and demands

Multicommodity Flow

Can this be done?

Multicommodity Flow is an LP problem

The problem is always feasible and bounded,�and hence has an optimal solution.

Note how quickly we were able to adapt the�LP formulations of the various flow problems we considered.

END OF �SEGMENT 12

LINEAR PROGRAMMING�Segment 13

LP duals of:

Maximum flow

Minimum cost flow

Shortest Paths

The LP dual of Maximum Flow

Before taking the dual, we do a “trick”.�(Not essential, but slightly simplifies things.)

Maximum Flow – Primal LP

We assume that no edges enter the source,�and that no edges leave the sink.

For “convenience”, we measure the flow �going out of the source, rather then the flow going into the sink.

Maximum Flow – Primal and dual LPs

Maximum Flow – Primal and dual LPs

(P)

Maximum Flow – dual LP

What does it mean?

The capacity of a cut is the sum of �the capacities of the edges that cross the cut.

Maximum Flow – Minimum Cut

We shall soon prove theorem, �which is special case of the LP duality theorem.

The primal LP for Shortest Paths

The primal LP for the shortest paths problem is �a minimum cost flow problem with no capacities!

An optimal solution of (P) is easily �obtained from a shortest paths tree.

Corollary: (P) always has an �integral optimal solution.

(P)

END OF �SEGMENT 13

END OF �LINEAR PROGRAMMING

Transportation Problem (TP) and Assignment Problem (AP)

(special cases of Linear Programming)

1. Transportation Problem (TP)

Distributing any commodity from any group of supply centers, called sources, to any group of receiving centers, called destinations, in such a way as to minimize the total distribution cost (shipping cost).

1. Transportation Problem (TP)

Total supply must equal total demand.

If total supply exceeds total demand, a dummy destination, whose demand equals the difference between the total supply and total demand is created. Similarly if total supply is less than total demand, a dummy source is created, whose supply

equals the difference.

All unit shipping costs into a dummy destination or out of a dummy source are 0.

Example 1:

Example 2:

Transportation Tableau:

1. Northwest Corner Starting Procedure

1. Select the remaining variable in the upper left (northwest) corner and note the supply remaining in the row, s, and the demand remaining in the column, d.

2. Allocate the minimum of s or d to this variable. If this minimum is s, eliminate all variables in its row from future consideration and reduce the demand in its column by s; if the minimum is d, eliminate all variables in the column from future consideration and reduce the supply in its row by d.

REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN ALLOCATED.

​

Initial Solution Procedure:

Total sipping cost = 2250

2. Least Cost Starting Procedure

1. For the remaining variable with the lowest unit cost, determine the remaining supply left in its row, s, and the remaining demand left in its column, d (break ties arbitrarily).

2. Allocate the minimum of s or d to this variable. If this minimum is s, eliminate all variables in its row from future consideration and reduce the demand in its column by s; if the minimum is d, eliminate all variables in the column from future consideration and reduce the supply in its row by d.

REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN ALLOCATED.

​

Total sipping cost = 2065

3. Vogel’s Approximation Method Starting Procedure

1. For each remaining row and column, determine the difference between the lowest two remaining costs; these are called the row and column penalties.

2. Select the row or column with the largest penalty found in step 1 and note the supply remaining for its row, s, and the demand remaining in its column, d.

3. Allocate the minimum of s or d to the variable in the selected row or column with the lowest remaining unit cost. If this minimum is s, eliminate all variables in its row from future consideration and reduce the demand in its column by s; if the minimum is d, eliminate all variables in the column from future consideration and reduce the supply in its row by d.

REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN ALLOCATED.

​

Total sipping cost = 2030

Solving TP – Transportation Simplex Method

1. Find the current C_ij–Z_ij values for each nonbasic variable and select the one with the most negative C_ij–Z_ij value as the entering variable; if all C_ij–Z_ij values are nonnegative, the current solution is optimal.

2. Determine which basic variable reaches 0 first when the entering variable is increased.

3. Determine a new basic solution and repeat the steps.

​

Step 1: Determine the C_ij–Z_ij Values for the Nonbasic Variables

​

1. If U_i is the dual variable associated with the i-th supply constraint, and V_j is the dual variable associated with the j-th demand constraint, then for shipments from node i to node j, one can find the corresponding Z_ij value by Z_ij = U_i - V_j. Thus the C_ij–Z_ij value for variable X_ij is found by

C_ij - Z_ij = C_ij - (U_i - V_j) = C_ij - U_i + V_j

2. Given that there is a redundant equation among the m n constraints (and any of the m n constraints can be considered the redundant one), one can show that the U_i or V_j associated with the redundant equation is 0. Thus one U_i or V_j can arbitrarily be selected and set to 0. Arbitrarily choose U₁ = 0.

​

3. Since the C_ij–Z_ij values for basic variables are 0 (i.e., C_ij - U_i + V_j = 0 for basic variables), we can easily solve for the remaining values of the U_i’s and V_j’s from the m + n - 1 equations for the basic variables.

​

​

4. Once the U_i’s and V_j’s have been determined, the C_ij–Z_ij values for the nonbasic variables can be calculated by

C_ij - Z_ij = C_ij - U_i + V_j

​

Non-basic cells:

Note: X₁₃ is the entering variable.

Step 2: Determine Which Current Basic Variable Reaches 0 First

​

Note: 1. Cycle property

2. X₁₂ is the leaving variable

Step 3: Determine the Next Transportation Tableau

​

Total shipping cost = 2020

{Improvement = 2 (-5) = 10 }

Transportation Simplex Method

Find an initial basic feasible solution by some starting procedure. Then,

1. Set U₁ 0. Solve for the other U_i’s and V_j’s by:

C_ij – U_i + V_j = 0 for basic variables.

Then calculate the C_ij–Z_ij values for nonbasic variables by:

C_ij – Z_ij = C_ij – U_i + V_j

Choose the nonbasic variable with the most negative C_ij–Z_ij value as the entering variable. If all C_ij–Z_ij values are nonnegative, STOP; the current solution is optimal.

2. Find the cycle that includes the entering variable and some of the BASIC variables. Alternating positive and negative changes on the cycle, determine the “change amount” as the smallest allocation on the cycle at which a subtraction will be made.

3. Modify the allocations to the variables of the cycle found in step 2 by the “change amount” and return to step 1.

​

Note: there must be m + n - 1 basic variables for the transportation simplex method to work!

=> Add dummy source or dummy destination, if necessary

(m=# of sources and n=# of destinations)

​

2. The Assignment Problem (AP) —

a special case of TP with m=n and s_i=d_j for all i, and j.

​

The Hungarian Algorithm

=> solving the assignment problem of a least

cost assignment of m workers to m jobs

​

Assumptions:

1. There is a cost assignment matrix for the m “people” to be assigned to m “tasks.” (If necessary dummy rows or columns consisting of all 0’s are added so that the numbers of people and tasks are the same.)

2. All costs are nonnegative.

3. The problem is a minimization problem.

​

The Hungarian Algorithm

Initialization

1. For each row, subtract the minimum number from all numbers in that row.

2. In the resulting matrix, subtract the minimum number in each column from all numbers in the column.

​

Iterative Steps

1. Make as many 0 cost assignments as possible. If all workers are assigned, STOP; this is the minimum cost assignment. Otherwise draw the minimum number of horizontal and vertical lines necessary to cover all 0’s in the matrix. (A method for making the maximum number of 0 cost assignments and drawing the minimum number of lines to cover all 0’s follows.)

2. Find the smallest value not covered by the lines; this number is the reduction value.

3. Subtract the reduction value from all numbers not covered by any lines. Add the reduction value to any number covered by both a horizontal and vertical line.

GO TO STEP 1.

​

For small problems, one can usually determine the maximum number of zero cost assignments by observation. For larger problems, the following procedure can be used:

Determining the Maximum Number of Zero-Cost Assignments

1. For each row, if only one 0 remains in the row, make that assignment and eliminate the row and column from consideration in the steps below.

2. For each column, if only one 0 remains, make that assignment and eliminate that row and column from consideration.

3. Repeat steps 1 and 2 until no more assignments can be made. (If 0’s remain, this means that there are at least two 0’s in each remaining row and column. Make an arbitrary assignment to one of these 0’s and repeat steps 1 and 2.)

​

Again, for small problems, the minimum number of lines required to cover all the 0’s can usually be determined by observation. The following procedure, based on network flow arguments, can be used for larger problems:

Drawing the Minimum Number of Lines to Cover All 0’s

1. Mark all rows with no assignments (with a “‧”).

2. For each row just marked, mark each column that has a 0 in that row (with a “‧”).

3. For each column just marked, mark each row that has an assignment in that column (with a “‧”).

4. Repeat steps 2 and 3 until no more marks can be made.

5. Draw lines through unmarked rows and marked columns.

​

Example:

Minimum uncovered

number

Minimum uncovered

number

CONVERSION OF A MAXIMIZATION PROBLEM TO A MINIMIZATION PROBLEM

​

The Hungarian algorithm works only if the matrix is a cost matrix. A maximization assignment problem can be converted to a minimization problem by creating a lost opportunity matrix. The problem then is to minimize the total lost opportunity.

​

Profit Matrix:

J1 J2 J3 J4

W1 67 58 90 55

W2 58 88 89 56

W3 74 99 80 22

(D) 0 0 0 0

​

The lost opportunity matrix given below is derived by subtracting each number in the J1 column from 74, each number in the J2 column from 99, each number in the J3 column from 90, and each number in the J4 from 56.

J1 J2 J3 J4

W1 7 41 0 1

W2 16 11 1 0

W3 0 0 10 34

(D) 74 99 90 56

​

The Hungarian algorithm can now be applied to this lost opportunity matrix to determine the maximum profit set of assignments.

​

Integer linear programming

• Optimization problems where design variables have to be integers are more difficult than ones with continuous variables.
• The degree of difficulty is particularly damaging for large number of variables:
• With continuous variables finding a local optimum increases linearly or quadratically with the number of variables.
• With integer variables it can increase exponentially (or non-polynomially): These problems are NP-hard.
• Problems with linear objective and linear constraints (Linear programming) are easier to solve.
• Furthermore: They do not have optima that are local but not global.

Formulation

• The standard form of an integer programming problem is

​

• Algorithm papers often limit themselves to standard form, but software usually allows the more general form

Example

Maximize fun time so that you make at least $75 and do not spend more than two hours.

Example Formulation

Only two variables are likely to be non-zero. Which do you expect them to be?

Continuous solution from Solver

• Without integer constraint, solution does not have to be integer

Integer solution

• Will rounding work?