Solving LP Models

Improving Search

Unimodal
Convex feasible region
Should be successful!

Special Form of Improving Search

Simplex method (now)

Interior point methods (later)
Part 3

IE 312

Simple Example

Top Brass Trophy Company

Makes trophies for

football

soccer

wood base, engraved plaque, brass football on top

$12 profit and uses 4 of wood
wood base, engraved plaque, soccer ball on top
$9 profit and uses 2 of wood

Current stock

1000 footballs, 1500 soccer balls, 1750 plaques,

and 4800 feet of wood

Part 3

IE 312

Formulation
max 12 x1 9 x2
x1 1000
s.t.
x2 1500
x1 x2 1750
4 x1 2 x2 4800
x1 , x2 0
Part 3

IE 312

Graphical Solution
4 x1 2 x2 4800

2000

x1 1500
x2 1500

1500

Optimal Solution
1000
x1 0
x1 x2 1750

500

x2 0

Part 3

500

1000

1500

2000

IE 312

Feasible Solutions

Feasible solution is a

boundary point if at least one inequality

constraint that can be strict is active
interior point if no such constraints are
active

Extreme points of convex sets do

not lie within the line segment of any
other points in the set
Part 3

IE 312

Example
2000
1500

1000

500

500

Part 3

1000

1500

2000

IE 312

Optimal Solutions

Every optimal solution is a boundary

point

We can find an improving direction whenever

we are at an interior point

If optimum unique the it must be an

extreme point of the feasible region

If optimal solution exist, an optimal

extreme point exists
Part 3

IE 312

LP Standard Form

Easier if we agree on exactly what

a LP should look like
Standard form

only equality main constraints

only nonnegative variables
variables appear at most once in lefthand-side and objective function
all constants appear on right hand side
Part 3

IE 312

Converting to Standard

Inequality constraints

Add nonnegative, zero-cost slack

variables
Add in inequalities
Subtract in inequalities

Variables not nonnegative

nonpositive - substitute with negatives

unrestrictive sign (URS) - substitute
difference of two nonnegative variables
Part 3

IE 312

Top Brass Model

max 12 x1 9 x2
x1 x3 1000
s.t.
x2 x4 1500
x1 x2 x5 1750
4 x1 2 x2 x6 4800
x1 , x2 , x3 , x4 , x5 , x6 0
Part 3

IE 312

10

Why?

Feasible directions

Equality constraints

Always active

Inequality constraints

Check only if active

Keep track of active constraints

May or may not be active

Prefer equality constraints!

Part 3

IE 312

11

Standard Notation
x j jth decision variable
c j cost coefficient of x j
aij constraint coefficient of x j in ith constraint
bi right - hand - side of ith constraint
m number of constraints
n number of decision variables
Part 3

IE 312

12

LP Standard Form

In standard notationm
min/ max

c x
j 1
n

s.t.

a x
j 1

ij

b j , i

x j 0, j

In matrix notation
min/ max c x
s.t.
Ax b
x0

Part 3

IE 312

13

Write in Matrix Form

max 30 x1 120 x2 4 x3

2 x1 x2 5 x3 x4 55

s.t.

x1 x3 x5 0
2 x2 18 x3 50
x1 , x2 , x3 , x4 , x5 0
c(

Part 3

IE 312

14

Extreme Points

Know that an extreme point

optimum exists
Will search trough extreme points
An extreme point is define by a set
of constraints that are active
simultaneously
Part 3

IE 312

15

Improving Search

Move from one extreme point to a

neighboring extreme point
Extreme points are adjacent if they
are defined by sets of active
constraints that differ by only one
element
An edge is a line segment determined
by a set of active constraints
Part 3

IE 312

16

Basic Solutions

Extreme points are defined by set of

active nonnegativity constraints

A basic solution is a solution that

is obtained by fixing enough
variable to be equal to zero, so that
the equality constraints have a
unique solution
Part 3

IE 312

17

Example
x1 x3 1000

x1 x3 1000
x2 x4 1500
x1 x2 x5 1750
4 x1 2 x2 x6 4800

x2 x4 1500
x1 x2 0 1750
4 x1 2 x2 0 4800

Choose x1, x2, x3, x4 to be basic

x (650,1100,350,400,0,0)
Part 3

IE 312

18

Where is the Basic Solution?

x (650,1100,350,400,0,0)

2000
1500

1000

500

500

Part 3

1000

1500

2000

IE 312

19

Example

Compute the basic solution for x1 and x2

4 x1 x2
x3 1
basis:
3x1 2 x2 2 x3 8
x1 ,
x2 ,
x3 , 0

Solve
4 x1 x2 1
3 x1 2 x2 8
Part 3

x1 1
x2 3
IE 312

20

Existence of Basis Solutions

Remember linear algebra?

A basis solution exists if and only if

the columns of corresponding
equality constraint form a basis
(in other words, a largest possible
linearly independent collection)
Part 3

IE 312

21

Checking

The determinant of a square matrix

D is
( j 1)

det(D) (1)

d1 j det(D j )

A matrix is singular if its determinant

= 0 and otherwise nonsingular
Need to check that the matrix is
nonsingular
Part 3

IE 312

22

Example

Check whether basic solutions exist for

4 x1 8 x2 x3 15
x1 2 x2 10
x1 , x2 , x3 0

Part 3

IE 312

23

Basic Feasible Solutions

A basic feasible solution to a LP

is a basic solution that satisfies all
the nonnegativity contraints

The basic feasible solutions

correspond exactly to the extreme
points of the feasible region
Part 3

IE 312

24

Example Problem

Suppose we have x3, x4, x5 as slack

variables in the following LP:

x1 x2 x3 0

x1 x4 2
x2 x5 3
x1 ,..., x5 0

Lets plot the original problem, compute

the basic solutions and check feasibility
Part 3

IE 312

25

Solution Algorithm

Simplex Algorithm

Variant of improving search

Standard display:

x1
max c 12
1
0
A
1
4
Part 3

x2 x3 x4 x5 x6
9 0 0 0 0
0 1 0 0 0
1 0 1 0 0
1 0 0 1 0
2 0 0 0 1
IE 312

b
1000
1500
1750
4800
26

Simplex Algorithm

Starting point

A basic feasible solution (extreme point)

Direction

Follow an edge to adjacent extreme

point:

Increase one nonbasic variable

Compute changes needed to preserve
equality constraints

One direction for each nonbasic variable

Part 3

IE 312

27

Top Brass Example

x1
max c 12
1
0
A
1
4
N
x (0)
0

Initial solution
Part 3

x2 x3
x4
x5
x6
9
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
1
0
2
0
0
0
1
N
B
B
B
B
0 1000 1500 1750 4800

b
1000
1500
1750
4800

Basic variables
IE 312

28

Looking in All Directions

x1
max c 12
1
0
A
1
4
N
x (0)
0
1
x 1
x 2

x2 x3
x4
x5
x6
9
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
1
0
2
0
0
0
1
N
B
B
B
B
0 1000 1500 1750 4800
0
-1
0
-1
-4
1

Can increase either

one of those
Part 3

-1

-1

b
1000
1500
1750
4800

-2

Must adjust these!

IE 312

29

So Many Choices ...

Want to try to improve the objective

n

f ( x) c x c j x j
j 1

The reduced cost of a nonbasic variable:

c j c x

Want

c j 0 if maximization
c j 0 if minimization
Part 3

IE 312

Defines
improving
direction
30

Top Brass Example

Improving x1 gives

c x
c1 12 9 0 0 0 0 1 0 1 0 1 4
12 0

Improving x2 gives

c x
c2 12 9 0 0 0 0 0 1 0 1 1 2
90

Both directions are improving directions!

Part 3

IE 312

31

Where and How Far?

Any improving direction will do

If no component is negative
Improve forever - unbounded!
Otherwise, compute the minimum
(t )
ratio
x j

min
: x j 0
x j

Part 3

IE 312

32

Computing Minimum Ratio

x1 x2 x3
x4
x5
x6
N N
B
B
B
B
x (0) 0 0 1000 1500 1750 4800
-1
0
-1
-4
x 1 0
1000
1750 4800
-(-1)
-(-1) -(-4)

min

x (jt )
x j

: x j 0

1000 1750 4800

min
,
,
1000
1
4
1

Part 3

IE 312

33

Moving to New Solution

x

(1)

x x
0 0 1000 1500 1750 4800
1000 1 0 1 0 1 4
100 0 0 0 1500 1750 4800
(0)

Part 3

IE 312

34

Updating Basis

New basic variable

Nonbasic variable generating

direction

New nonbasic variable(s)

Basic variables fixing the step size

Part 3

IE 312

35

What Did We Do?

2000
1500

1000

500

x (0)

x (1)
500

Part 3

1000

1500

2000

IE 312

36

Where Will We Go?

2000

Optimum in three steps!

1500

1000

x ( 2)

500

x (0)

x (1)
500

Part 3

Why is this
guaranteed?

( 3)

1000

1500

2000

IE 312

37

Simplex Algorithm
(Simple)
Step 0: Initialization. Choose starting feasible basis, construct basic solution x(0),
and set t=0
Step 1: Simplex Directions. Construct directions Dx associated with increasing
each nonbasic variable xj and compute the reduced cost cj =c x.
Step 2: Optimality. If no direction is improving, then stop; otherwise choose any
direction x(t+1) corresponding to some basic variable xp.
Step 3: Step Size. If no limit on move in direction x(t+1) then stop; otherwise
choose variable xr such that

x (jt )
xr( t )
( t 1)
min
: x j 0
( t 1)
( t 1)
x r
x j

xr( t )
and set
xr( t 1)

Step 4: New Point and Basis. Compute the new solution

x (t 1) x ( t ) x ( t 1)

and replace xr in the basis with xp. Let t = t+1 and go to Step 1.

Part 3

IE 312

38

Stopping

The algorithm stop when one of two

criteria is met:

In Step 2 if no improving direction

exists, which implies local optimum,
which implied global optimum

In Step 3 if no limit on improvement,

which implies problem is unbounded
Part 3

IE 312

39

Optimization Software

Spreadsheet (e.g, MS Excel with Whats Best!)

Optimizers (e.g., LINDO)

Combination

Modeling Language

Solvers

Either together (e.g., LINGO) or separate (e.g.,

GAMS with CPLEX)

LINDO and LINGO are in Room 0010 (OR Lab)

Also on disk with your book

Part 3

IE 312

40

LINDO

The main software that Ill ask you to use is

called LINDO
Solves linear programs (LP), integer
programs (IP), and quadratic programs (QP)
We will look at many of its more advanced
features later on, but as of yet we havent
learned many of the concepts that we need

Part 3

IE 312

41

Example
max 12 x1 9 x2
x1 x3 1000
s.t.
x2 x4 1500
x1 x2 x5 1750
4 x1 2 x2 x6 4800
x1 , x2 , x3 , x4 , x5 , x6 0
Part 3

IE 312

42

LINDO Program
MAX12x1+9x2

ST

x1+x2=1000
x2+x4=1500
x1+x2+x5=1750
4x1+2x2+x6=4800
x1>=0
x2>=0
x3>=0
x4>=0
x5>=0
x6>=0

END

Part 3

IE 312

43

Part 3

IE 312

44

Part 3

IE 312

45

Output
LPOPTIMUMFOUNDATSTEP4
OBJECTIVEFUNCTIONVALUE
1)12000.00
VARIABLEVALUEREDUCEDCOST
X11000.0000000.000000
X20.0000003.000000
X41500.0000000.000000
X5750.0000000.000000
X6800.0000000.000000
X30.0000000.000000

Part 3

IE 312

46

Output (cont.)
ROWSLACKORSURPLUSDUALPRICES
2)0.00000012.000000
3)0.0000000.000000
4)0.0000000.000000
5)0.0000000.000000
6)1000.0000000.000000
7)0.0000000.000000
8)0.0000000.000000
9)1500.0000000.000000
10)750.0000000.000000
11)800.0000000.000000
NO.ITERATIONS=4
Part 3

IE 312

47

LINDO: Basic Syntax

Objective Function Syntax: Start all

models with MAX or MIN
Variable Names: Limited to 8
characters
Constraint Name: Terminated with a
parenthesis
Recognized Operators (+, -, >, <, =)
Order of Precedence: Parentheses not
recognized
Part 3

IE 312

48

Syntax (cont.)

Adding Comment: Start with an

exclamation mark
Splitting lines in a model: Permitted in
LINDO
Case Sensitivity: LINDO has none
Right-hand Side Syntax: Only constant
values
Left-hand Side Syntax: Only variables and
their coefficients
Part 3

IE 312

49

Why Modeling Language?

More to learn!
More complicated to use than
LINDO (at least at first glance)
Advantages

Natural representations
Similar to mathematical notation
Can enter many terms simultaneously
Much faster and easier to read
Part 3

IE 312

50

Why Solvers?

Best commercial software has modeling

language and solvers separated

Advantages:

Select solver that is best for your application

Learn one modeling language use any solver

Buy 3rd party solvers or write your own!

Part 3

IE 312

51

Example Problem
Biscos new sugar-free, fat-free chocolate squares are so popular that the company
cnnot keep up with demand. Regional demands shown in the following table total
2000 cases per week, but Bisco can produce only 60% of that number.
Demand
Profit

NE

SE

MW

620
1.6

490
1.4

510
1.9

380
1.2

The table also shows the different profit levels per case experienced in the regions
due to competition and consumer tastes. Bisco wants to find a maximum profit
plan that fulfills between 50% and 70% of each regions demand.

Part 3

IE 312

52

Problem Formulation
4

max pi xi
i 1

x
i 1

1200

li xi ui , i 1,2,3,4
Part 3

IE 312

53

LINDO Solution

max

1.60 x1 + 1.40 x2 + 1.90 x3 + 1.20 x4

st
x1
x1
x1
x2
x2
x3
x3
x4
x5
end

+ x2 + x3 + x4 <=1200
>= 310
<= 434
>= 245
<= 343
>= 255
<= 357
>= 190
<= 266
Part 3

IE 312

54

LINGO Solution

Capacity constraint
@SUM(REGIONS(I): CASES(I))
<=1200;

Minimum/maximum cases
@FOR(REGIONS(I):
CASES(I) <= UBOUND;
CASES(I) >= LBOUND);
Part 3

IE 312

55

LINGO Solution

Objective function
MAX = @SUM(REGIONS(I):
PROFIT*CASES(I));

We also need to define REGIONS,

CASES, etc, and type in the data.
Part 3

IE 312

56

LINGO Solution

Defining sets
SETS:
REGIONS / NE SE MW W/: LBOUND,
UBOUND, PROFIT, CASES;
ENDSETS

Part 3

IE 312

57

LINGO Solution

Enter the data

DATA:
LBOUND = 310 245 255 190;
UBOUND = 434 343 357 266;
PROFIT = 1.6 1.4 1.9 1.2;
ENDDATA
Part 3

IE 312

58

Sensitivity Analysis

Basic Question: How does our solution

change as the input parameters change?

The objective function?

The optimal values of decision variables?

More/less profit or cost

Make different decisions!

Why?

Only have estimates of input parameters

May want to change input parameters

Part 3

IE 312

59

What We Know

Qualitative Answers for All Problems

Quantitative Answers for Linear
Programs (LP)

Dual program
Same input parameters
Decision variables give sensitivities
Dual prices
Easy to set up
Theory is somewhat complicated

Part 3

IE 312

60

Back to Example Problem

Biscos new sugar-free, fat-free chocolate squares are so popular that the company
cnnot keep up with demand. Regional demands shown in the following table total
2000 cases per week, but Bisco can produce only 60% of that number.
Demand
Profit

NE

SE

MW

620
1.6

490
1.4

510
1.9

380
1.2

The table also shows the different profit levels per case experienced in the regions
due to competition and consumer tastes. Bisco wants to find a maximum profit
plan that fulfills between 50% and 70% of each regions demand.

Part 3

IE 312

61

LINDO Formulation
max
st

1.60 x1 + 1.40 x2 + 1.90 x3 + 1.20 x4

x1
x1
x1
x2
x2
x3
x3
x4
x5

end

+ x2 + x3 + x4 <=1200
>= 310
<= 434
>= 245
<= 343
>= 255
<= 357
>= 190
<= 266

Part 3

IE 312

62

LINDO Solution (second

half)
ROW

SLACK OR SURPLUS

DUAL PRICES

2)

0.000000

1.600000

3)

98.000000

0.000000

4)

26.000000

0.000000

5)

0.000000

-0.200000

6)

98.000000

0.000000

7)

102.000000

0.000000

8)

0.000000

0.300000

9)

0.000000

-0.400000

10)

266.000000

0.000000

Part 3

IE 312

63

Dual Prices

The Dual is Automatically Formed

Report dual prices

Also in LINGO
Also in (all) other optimization software
Gives us sensitivities to RHS parameter
Know how much objective function will
change

When will the optimal solution change?

Need to select that we want sensitivity
analysis
Part 3

IE 312

64

LINDO Sensitivity Analysis

(part)
RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE

CURRENT

ALLOWABLE

ALLOWABLE

COEF

INCREASE

DECREASE

X1

1.600000

0.300000

0.200000

X2

1.400000

0.200000

INFINITY

X3

1.900000

INFINITY

0.300000

X4

1.200000

0.400000

INFINITY

X5

0.000000

0.000000

INFINITY

Part 3

IE 312

65

Interpretation

As long as prices for the NE region

are between $1.4 and $1.9, we
want to sell the same quantity to
each region, etc.

Part 3

IE 312

66

Example
An insurance company is introducing two new
product lines: special risk insurance and mortgages.
The expected profit is $5 per unit on special risk
insurance and $2 per unit on mortgages.
Management wishes to establish a sales target for the
new product lines to maximize the expected profit.
The work requirements are as follows:
Part 3

IE 312

67

LINDO Formulation
max 5 x1 + 2 x2
st
3 x1 + 2 x2 <= 2400
x2 <= 800
2 x1 <= 1200
x1 >=0
x2 >=0
Part 3

IE 312

68

Graphical Solution
800
700
600
500
400
300
200
100

100 200 300 400 500 600 700 800

Part 3

IE 312

69

Solution
VARIABLE

VALUE

REDUCED COST

X1

600.000000

0.000000

X2

300.000000

0.000000

ROW

SLACK OR SURPLUS

DUAL PRICES

2)

0.000000

1.000000

3)

500.000000

0.000000

4)

0.000000

1.000000

5)

600.000000

0.000000

6)

300.000000

0.000000

Part 3

IE 312

70

Sensitivity Analysis
RANGES IN WHICH THE BASIS IS UNCHANGED:

CURRENT
COEF
5.000000
2.000000

OBJ COEFFICIENT RANGES

ALLOWABLE
ALLOWABLE
INCREASE
DECREASE
INFINITY
2.000000
1.333333
2.000000

CURRENT
RHS
2400.000000
800.000000
1200.000000
0.000000
0.000000

RIGHTHAND SIDE RANGES

ALLOWABLE
ALLOWABLE
INCREASE
DECREASE
1000.000000
600.000000
INFINITY
500.000000
400.000000
666.666687
600.000000
INFINITY
300.000000
INFINITY

VARIABLE
X1
X2

ROW
2
3
4
5
6

Part 3

IE 312

71

New Decisions!
800
700
600
500

Optimum
Moves!

400
300
200
100

100 200 300 400 500 600 700 800

Part 3

IE 312

72

What-If ? Solve New

Problem
max 5 x1 + 2 x2
st
3 x1 + 2 x2 <= 2400
x2 <= 290
2 x1 <= 1200
x1 >=0
x2 >=0
Part 3

IE 312

73

New Solution
VARIABLE

VALUE

REDUCED COST

X1

600.000000

0.000000

X2

290.000000

0.000000

ROW

SLACK OR SURPLUS

DUAL PRICES

2)

20.000000

0.000000

3)

0.000000

2.000000

4)

0.000000

2.500000

5)

600.000000

0.000000

6)

290.000000

0.000000

Part 3

IE 312

74

Interior Point Methods

Simplex always stays on the boundary

Can take short cuts across the interior

Interior point methods

More effort in each move

More improvement in each move

Much faster for large problems

Part 3

IE 312

75

Simple Example

Frannies Firewood sells up to 3 cords of

firewood to two customers

One will pay $90 per half-cord

Other will pay $150 per full cord

x1 number of half - cords sold to customer 1

x2 number of cords sold to customer 2

max 90 x1 150 x2
1
s.t
x1 x2 3
2
x1 , x2 0
Part 3

IE 312

76

Graphical Solution
x2

4
3
2
x* 6 0

1
1
Part 3

IE 312

x1
77

Improving Directions

Which direction improves the objective

function the most?
The gradient
f ( x ) c x c
Direction:

x c if
x c if
Part 3

max c x
min c x
IE 312

78

Most Improving Direction?

min 4 x1 19 x2 x3 ?

max 2 x1 x2 79 x3 ?

Part 3

IE 312

79

Back to Example
x2

4
3

50
26

53

26

x (1)

x* 6 0

1
x

(0)

1
1

Part 3

IE 312

x1
80

Maintaining Feasibility

At the initial point all directions are

feasible because it is an interior point
At the new point we have to make sure
that a direction x at x(1) satisfies

1
x1 x2 0
2

Interior point algorithms begin inside and

move through the interior, reaching the
boundary only at an optimal solution
Part 3

IE 312

81

Valid Interior Point Search?

2000
1500

1000

500

500

Part 3

1000

1500

2000

IE 312

82

Valid Interior Point Search?

2000
1500

1000

500

500

Part 3

1000

1500

2000

IE 312

83

Valid Interior Point Search?

2000
1500

1000

500

500

Part 3

1000

1500

2000

IE 312

84

LP Standard Form

For Simplex used the form

min/ max c x
s.t.
Ax b
x0

In Frannies Firewood
max
s.t

Part 3

90 x1 150 x2

1
x1 x2 x3 3
2
x1 , x2 , x3 0
IE 312

85

Benefits of Standard
Form?

In Simplex:

Here quite similar:

Made easy to check which variables are basic,

non-basic, etc.
Needed to know which solutions are on boundary
Know which are not on boundary
Check that nonnegativity constraints are strict!

A feasible solution to standard LP is interior

point if every component is strictly positive
Part 3

IE 312

86

Interior Points?
min
5 x1 2 x3 8 x4
s.t 2 x1 3 x2 x3 10
6 x1 2 x4 12
x1 , x2 , x3 , x4 0
x (1) 8 0 6 18

Part 3

x ( 2 ) 4 1 1 6 x ( 3) 3 3 1 6

IE 312

87

Projections

Must satisfy main equality constraints

Ax b
Ax 0

Want direction x that satisfies this equation

and is as nearly d as possible
The projection of a vector d onto a system of
equalities is the vector that satisfies the
constraints and minimizes the total squared
difference between the components
Part 3

IE 312

88

Obtaining Projection

The projection of d onto Ax=0 is

x Pd
where

T 1

P I A ( AA ) A
T

is the projection matrix.

Part 3

IE 312

89

Example: Frannies Firewood

1
2

1 1

1
2
T
A 1

AA T

9
4

1
2 4 1
T
T 1
A AA
A 1

9 2
1

9
2

1 1
9

2
9
4
9
4
9

9
4
9
4

P I A T AA

Part 3

T 1

A 0
0

0
1
0

9
2

9
2

2
9
4
9
4
9

2
8

9
9
4
2

9
9

4
2

9
9

IE 312

2
9
5
9
4

9
4

9
5

90

Example

The cost vector is c=(90 150 0)

x Pd
8

9
2

9
2

9
Part 3

9
5
9
4

2

9
4

9
5

3

5
0

IE 312

14

9
19

9
26

9

91

Improvement

The projection matrix is design to

make an improving direction feasible
with minimum changes
Is it still an improving direction? Yes!
The projection x=Pc of c onto Ax=b
is an improving direction at every x
Part 3

IE 312

92

Sample Exercise
max
s.t.

x1 x2 x3
x1 x3 1
2 x2 x3 5
x1 , x2 , x3 0

Determine the direction d of most rapid improvement

Project it onto the main equality constraints to get x
Verify that the move direction x is feasible
Verify that the move direction x is improving

Part 3

IE 312

93