Integer/Binary

Group 4 Integer
Erin Romfo Programming
Anthony Rende
Joe Redmond Presentation
 Integer Linear Programs
 In an All-Integer Linear Program all the
variables are integers.
 In LP Relaxation the integer requirements
are removed from the program
 In a Mixed-Integer Linear Program some
variables, but not all, are integers.
 In a Binary Integer Linear Program the
variables are restricted to a value of 0 or
1.
Some Applications of Integer
Linear Programming:
 Capital budgeting – capital is limited and
management would like to select the most
profitable projects.
 Fixed cost – there is a fixed cost associated
with production setup and a maximum
production quantity for the products.
 Distribution system design – determine the
best plant locations and to determine how
much to ship from the plants to distribution
centers.
 Location problem – minimum amount of locations
to do business and serve the largest area.
 Product design & market share – use the
preferences of prospective consumers/buyers to
determine what to produce.
 All-Integer Problem
To help illustrate this problem, let’s use our
favorite example of tables and chairs. T&C
Company wants to maximize their profits.
They make $10 for every table and $3 for
every chair. Employee #1 can make 6
tables and 7 chairs, but can’t work more
than 40 hours. Employee #2 can make 3
tables and 1 chair, but can’t work more
than 11 hours.
 LP Relaxation
Model: Optimal Solution:

Max 10x₁ + 3x₂ OF = 36.66667

x₁ = 3.666667
s.t. 6x₁ + 7x₂ ≤ 40 x₂ = 0
3x₁ + x₂ ≤ 11
x₁, x₂ ≥ 0
 Graph of LP Relaxation
x₂
Problem
3x₁ + x₂ ≤ 11

10x₁ + 3x₂
Tables

6x₁ + 7x₂ ≤ 40

LP Optimal Solution

x₁
Chairs
 Rounding Up and Rounding
Down
 In this situation rounding x₁ up from
3.666667 to 4 would give a solution
outside the feasible region.
 Rounding down x₁ from 3.666667 to 3
would provide a feasible solution, but not
necessarily the optimal solution.
 Complete Enumeration of
Feasible Solutions
x₁ x₂ 10x₁ + 3x₂ x₁ x₂ 10x₁ + 3x₂
1. 0 0 0 11. 2 2 26
2. 1 0 10 12. 3 2 36
3. 2 0 20 13. 0 3 9
4. 3 0 30
14. 1 3 19
5. 0 1 3
6. 1 1 13 15. 2 3 29
7. 2 1 23 16. 0 4 12
8. 3 1 33 17. 1 4 22
9. 0 2 6 18. 2 4 32
10. 1 2 16 19. 0 5 15
 Calculating the Optimal
Solution
So, if we take the original model and add the
integer constraint we can find the optimal
solution much quicker.

Max 10x₁ + 3x₂

s.t. 6x₁ + 7x₂ ≤ 40

3x₁ + x₂ ≤ 11
x₁, x₂ ≥ 0 and integer
 Input into LINGO
Model:
!Objective Function;
Max = 10*x1 + 3*x2;
!Subject to;
6*x1 + 7*x2 <= 40;
3*x1 + x2 <= 11;
@Gin (x1);
@Gin (x2);
End
 LINGO Results and Graph
Global optimal solution found.
Objective value: 36.00000
Objective bound: 36.00000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 0
Elapsed runtime seconds: 0.05

Model Class: PILP

Total variables: 2
Nonlinear variables: 0
Integer variables: 2

Total constraints: 3
Nonlinear constraints: 0
All-Integer Optimal
Total nonzeros:
Nonlinear nonzeros:
6
0
Solution (3,2)

Variable Value Reduced Cost

X1 3.000000 -10.00000
X2 2.000000 -3.000000

Row Slack or Surplus Dual Price

1 36.00000 1.000000
2 8.000000 0.000000
3 0.000000 0.000000
 Binary Integer Programming
Problem
CHB Inc., is a bank holding company that is
evaluating the potential for expanding into
a 13-county region in the southwestern part
of the state. State law permits establishing
branches in any county that is adjacent to
a county in which a PPB (principal place of
business) is located. The following map
shows the 13-county region with the
population of each county indicated.
Map
 Table of Counties
Counties Under Consideration Adjacent Counties
1 2,3
2 1,3,4,6,7
3 1,2,4,5
4 2,3,5,6,8
5 3,4,8,9,10
6 2,4,7,8,11
7 2,6,11
8 4,5,6,9,11
9 5,8,10,11,12
10 5,9,12
11 6,7,8,9,12,13
12 9,10,11,13
13 11,12
Decision Variables and
Problem Formulation
xᵢ = County, 1 if established and 0 if not.

Min x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃

s.t. x₁ + x₂ + x₃ ≥ 1
x₁ + x₂ + x₃ + x₄ + x₆ + x₇ ≥ 1
x₁ + x₂ + x₃ + x₄ + x₅ ≥ 1
x₂ + x₃ + x₄ + x₅ + x₆ + x₈ ≥ 1
x₃ + x₄ + x₅ + x₈ + x₉ + x₁₀ ≥ 1
x₂ + x₄ + x₆ + x₇ + x₈ + x₁₁ ≥ 1
x₂ + x₆ + x₇ + x₁₁ ≥ 1
x₄ + x₅ + x₆ + x₈ + x₉ + x₁₁ ≥ 1
x₅ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ ≥ 1
x₅ + x₉ + x₁₀ + x₁₂ ≥ 1
x₆ + x₇ + x₈ + x₉ + x₁₁ + x₁₂ + x₁₃ ≥ 1
x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ ≥ 1
x₁₁ + x₁₂ + x₁₃ ≥ 1
xᵢ = 0,1
Objective Function;
LINGO Model
Min = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13;
!Subject to;
x1 + x2 + x3 >=1;
x1 + x2 +x3 + x4 + x6 + x7 >= 1;
x1 + x2 + x3 + x4 + x5 >= 1;
x2 + x3 + x4 + x5 + x6 + x8 >= 1;
x3 + x4 + x5 + x8 + x9 + x10 >= 1;
x2 + x4 + x6 + x7 + x8 + x11 >= 1;
x2 + x6 + x7 + x11 >= 1;
x4 + x5 + x6 + x8 + x9 + x11 >= 1;
x5 + x8 + x9 + x10 + x11 + x12 >= 1;
x5 + x9 + x10 + x12 >= 1;
x6 + x7 + x8 + x9 + x11 + x12 + x13 >= 1;
x9 + x10 + x11 + x12 + x13 >= 1;
x11 + x12 + x13 >= 1;
@Bin (x1);
@Bin (x2);
@Bin (x3);
@Bin (x4);
@Bin (x5);
@Bin (x6);
@Bin (x7);
@Bin (x8);
@Bin (x9);
@Bin (x10);
@Bin (x11);
@Bin (x12);
@Bin (x13);
End
LINGO Results
Variable Value Reduced Cost
X1 0.000000 1.000000
X2 0.000000 1.000000
X3 1.000000 1.000000
Global optimal solution found. X4 0.000000 1.000000
Objective value: 3.000000 X5 1.000000 1.000000
Objective bound: 3.000000 X6 0.000000 1.000000
Infeasibilities: 0.000000 X7 0.000000 1.000000
Extended solver steps: 0 X8 0.000000 1.000000
Total solver iterations: 0 X9 0.000000 1.000000
Elapsed runtime seconds: 0.05 X10 0.000000 1.000000
X11 1.000000 1.000000
Model Class: PILP X12 0.000000 1.000000
X13 0.000000 1.000000
Total variables: 13
Nonlinear variables: 0 Row Slack or Surplus Dual Price
Integer variables: 13 1 3.000000 -1.000000
2 0.000000 0.000000
Total constraints: 14 3 0.000000 0.000000
Nonlinear constraints: 0 4 1.000000 0.000000
5 1.000000 0.000000
Total nonzeros: 80 6 1.000000 0.000000
Nonlinear nonzeros: 0 7 0.000000 0.000000
8 0.000000 0.000000
9 1.000000 0.000000
10 1.000000 0.000000
11 0.000000 0.000000
12 0.000000 0.000000
13 0.000000 0.000000
14 0.000000 0.000000
Map of Branches to be Built
What if only one branch could
be built?
Min 195,000y₁ + 96,000y₂ + 87,000y₃ + 52,000y₄ + 233,000y₅ + 57,000y₆ + 117,000y₇ + 88,000y₈
+106,000 y₉ + 76,000y₁₀ + 95,000y₁₁ + 323,000y₁₂ + 175,000y₁₃

s.t. x₁ + x₂ + x₃ ≥ 1 - y₁
x₁ + x₂ + x₃ + x₄ + x₆ + x₇ ≥ 1 - y₂
x₁ + x₂ + x₃ + x₄ + x₅ ≥ 1 - y₃
x₂ + x₃ + x₄ + x₅ + x₆ + x₈ ≥ 1 - y₄
x₃ + x₄ + x₅ + x₈ + x₉ + x₁₀ ≥ 1 - y₅
x₂ + x₄ + x₆ + x₇ + x₈ + x₁₁ ≥ 1 - y₆
x₂ + x₆ + x₇ + x₁₁ ≥ 1 - y₇
x₄ + x₅ + x₆ + x₈ + x₉ + x₁₁ ≥ 1 - y₈
x₅ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ ≥ 1 - y₉
x₅ + x₉ + x₁₀ + x₁₂ ≥ 1 - y₁₀
x₆ + x₇ + x₈ + x₉ + x₁₁ + x₁₂ + x₁₃ ≥ 1 - y₁₁
x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ ≥ 1 - y₁₂
x₁₁ + x₁₂ + x₁₃ ≥ 1- y₁₃
x₁ + x₂ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ = 1
xᵢ and yᵢ = 0,1
 LINGO Results
Variable Value Reduced Cost
Global optimal solution found. Y1 1.000000 195000.0
Objective value: 739000.0 Y2
Y3
1.000000
1.000000
96000.00
87000.00
Objective bound: 739000.0 Y4
Y5
1.000000
1.000000
52000.00
233000.0
Infeasibilities: 0.000000 Y6
Y7
0.000000
0.000000
57000.00
117000.0
Extended solver steps: 0 Y8 0.000000 88000.00
Y9 0.000000 106000.0
Total solver iterations: 13 Y10 1.000000 76000.00
Y11 0.000000 95000.00
Elapsed runtime seconds: 0.06 Y12 0.000000 323000.0
Y13 0.000000 175000.0
X1 0.000000 0.000000
Model Class: PILP X2
X3
0.000000
0.000000
0.000000
0.000000
X4 0.000000 0.000000
X6 0.000000 0.000000
Total variables: 26 X7 0.000000 0.000000
X5 0.000000 0.000000
Nonlinear variables: 0 X8 0.000000 0.000000
X9 0.000000 0.000000
Integer variables: 26 X10 0.000000 0.000000
X11 1.000000 0.000000
X12 0.000000 0.000000
Total constraints: 15 X13 0.000000 0.000000

Nonlinear constraints: 0 Row

1
Slack or Surplus
739000.0
Dual Price
-1.000000
2 0.000000 0.000000
3 0.000000 0.000000
Total nonzeros: 106 4 0.000000 0.000000
5 0.000000 0.000000
Nonlinear nonzeros: 0 6 0.000000 0.000000
7 0.000000 0.000000
8 0.000000 0.000000
9 0.000000 0.000000
10 0.000000 0.000000
11 0.000000 0.000000
12 0.000000 0.000000
13 0.000000 0.000000
14 0.000000 0.000000
15 0.000000 0.000000
Total Population Served
 Conclusion
The problems that have been shown only
represent a couple of ways that Integer
and Binary Integer Programming can be
used in real world applications. There are so
many ways to use this programming it
would be impossible to illustrate them all!
The End