i 高等作業研究 Chapter 7 Integer Programming Models

高等作業研究
Chapter 7
Integer Programming Models
1
Chapter 7 Integer Programming Models
高等作業研究
In manufacturing, products are often indivisible, so a
production plan that calls for fractional output is not
acceptable.
There are also many situations that require logical decisions of
the form yes/no, go/no go, assign / don't assign.
Designers faced with selecting from a finite set of alternatives,
schedulers seeking the optimal sequence of activities, or
transportation planners searching for minimum cost vehicle
routes all face discrete decision problems.
2
Chapter 7 Integer Programming Models
高等作業研究
SITE SELECTION EXAMPLE
A manufacturer is planning to construct new
buildings at four local sites designated 1,2, 3, and
4. At each site, there are three possible building
designs labeled A, B, and C. There is also the
option of not using a site.
The problem is to select the optimal combination
of building sites and building designs.
Preliminary studies have determined the required
investment and net annual income for each of the
12 options.
3
Chapter 7 Integer Programming Models
高等作業研究
• The company has an investment budget of $100
million ($100M). The goal is to maximize total
annual income without exceeding the investment
budget .
4
Chapter 7 Integer Programming Models
高等作業研究
Let I = {A, B, C},
J= (1,2,3,4) be the set of site options.
1 if design i is used at site j
Let y ij  
for i  I and j  J
0 otherwise
Also, denote by pij the annual net income and by aij the
investment required for the design/site combination i,j.
As a first try, you propose the following model for
finding the maximum net annual income.
5
Chapter 7 Integer Programming Models
高等作業研究
Maximize z    pij y ij
iI jJ
  aij yij  100
subject to
iI jJ
y ij  {0,1}, i  I , j  J
the optimal solution is
yA1= yA3= yB3=yB4=yC1=1
with all other values of yij equal to zero and z = 40.
Of the available budget, $99M is used.
6
Chapter 7 Integer Programming Models
高等作業研究
You seem to have omitted some of the logic of the
problem, because two designs are built on the same
site—that is, Al and Cl, and also A3 and B3, are all
in the solution.
In addition, your supervisor now realizes that you
were not alerted to several other logical restrictions
imposed by the owners and architects—i.e.,
(a) site 2 must have a building;
(b) design A can be used at sites 1,2, and 3 only
if it is also selected for site 4;
(c) at most two of the designs may be included in
the plans.
7
Chapter 7 Integer Programming Models
高等作業研究
The following additional constraints are needed to
guarantee a feasible solution.
Site 2 must have a building:
y
iI
i2
1
There can be at most one building at each of the other sites:
 yij  1
for j  1,3,4
iI
8
Chapter 7 Integer Programming Models
高等作業研究
Design A can be used at sites 1,2, and 3 only if it is also
selected for site 4:
y A1  y A2  y A3  3y A4
To formulate the constraints associated with design selection,
three new binary variables are introduced.
1 if design i is used
for i  A, B, C
Let Wi = 
0 otherwise
9
Chapter 7 Integer Programming Models
高等作業研究
At most two designs may be used:
WA + WB + WC  2
Finally, the yij and wi variables must be tied together:
4
 yij  4wi
for i  A, B, C
j 1
the optimal solution is
yA1 = yA4 = yB2 = yB3 = wA =wB = 1
with all other variables equal to zero and z = 37.
All the budget is spent.
10
Chapter 7 Integer Programming Models
高等作業研究
Logical Constraints
Bound Constraints: yi=0 or 1 for i=1,2,…,n
The n decisions are mutually exclusive: y1 + y2 +…+yn  1
At most k in the subset may be chosen: y1 + y2 +…+yn  k
At least k in the subset must be chosen: y1 + y2 +…+yn  k
Exactly k must be chosen: y1 + y2 +…+yn = k
11
Chapter 7 Integer Programming Models
高等作業研究
Implication Constraints
Let w be a binary variable that corresponds to a
decision implied by one or more related decisions.
• Decision w is implied if any one of the other n decision
variables has a value of l:
y1 + y2 +…+yn  nw
12
Chapter 7 Integer Programming Models
高等作業研究
• Decision w is implied if all of the other decision
variables are 1:
y1 + y2 +…+yn
 n-1+w
• Decision w is implied if at least k of the other n
decision variables are 1:
y1 + y2 +…+yn
 (k-1)+[n-(k-1)]w
13
Chapter 7 Integer Programming Models
高等作業研究
Binary Variable Implied by a Real Variable
Consider the binary variable y representing the
decision whether or not to build a facility and
the real variable x representing the number of
products produced by the facility. A logical
constraint that restricts the variable x to be 0
unless y is 1 is
x  uy
where u is an upper bound on x.
14
Chapter 7 Integer Programming Models
高等作業研究
GENERAL CONSIDERATIONS
Model Structure
n
Maximize z =
c j x j
 
 
aij x j   aij x j   b ,i=1, . . .m

i
j 1
j  p 1
 
 
j 1
p
subject to
n
xj  0 and integer, j = 1,...,p, and xj > 0, j = p+ l,...,n
15
Chapter 7 Integer Programming Models
高等作業研究
The first p variables are restricted to integer values,
whereas the remaining n - p variables can assume any
nonnegative real values.
When all the variables are constrained to the values 0
and 1, this restriction allows us to represent binary
decisions such as yes/no and gives rise to what is
called a binary or 0-1 programming problem.
16
Chapter 7 Integer Programming Models
高等作業研究
Simple Transformations
Converting a General IP to a 0-1 Model
Although it is somewhat inefficient from a computational
point of view, it is possible to use only binary variables in IP
models.
A simple transformation replaces a bounded general integer
variable with a weighted sum of several binary variables.
Let x be an integer variable bounded by zero from below and
by u from above.
Let t be the smallest integer such mat 2t+1 > u.
17
Chapter 7 Integer Programming Models
高等作業研究
t
x= y1 +2 y2 +4y3
…+2ty
j
2
y j 1  u
t+1= 
j 0
yj= 0 or 1, j =1 ,..., t + l
where 2t  u < 2t+1
For example, if x is bounded by 15, then t = 3 (because
24 > 15  23).
The transformation is x = y1 + 2y2 + 4y3 + 8y4.
18
Chapter 7 Integer Programming Models
高等作業研究
Discrete Decision Values and Functions
Suppose that x can take on only one of a finite set of values—
i.e., x  D = {d1, d2,..., dr}. We can model this situation as
x= d1y1 +d2 y2 + d3y3…+ dryr
y1 + y2 +…+ yr= l
yj=0 or l , j=1,...,r
Ex: x  {5, 8, 13, 20}
19
Chapter 7 Integer Programming Models
高等作業研究
Complemented Variables
For some algorithms, it is necessary to have all positive
signs in the objective function. When only binary variables
appear in the model, replacing the corresponding variable
with its complement can reverse a negative coefficient. The
complement of binary variable xj is 1- xj which is also binary.
Ex. Z=x1-4x2+5x3
20
Chapter 7 Integer Programming Models
高等作業研究
SYSTEM DESIGN WITH FIXED CHARGES
Fixed Charge Model
In many situations, undertaking an activity means that a fixed
charge or setup cost is incurred in addition to the variable cost
associated with the level of the activity.
In the telecommunications network design problem, there is a
tradeoff between construction costs and operating costs for a
given demand. In a manufacturing problem, there is usually a
fixed charge for setting up a machine and a variable cost for each
item produced. The same is true for building and operating most
facilities.
21
Chapter 7 Integer Programming Models
高等作業研究
To construct a model for the network design problem, let xk be
the flow on proposed link k A'. The total cost for link k can be
modeled by the following nonlinear concave function.
 f k  ck x k
hk (xk )  
0
when xk  0
when xk  0
where fk is the fixed cost coefficient and ck is the variable cost
coefficient.
LP formulations cannot handle this kind of function directly.
22
Chapter 7 Integer Programming Models
高等作業研究
1 if link k is built
Let y k  
0 otherwise
for all k  A
When hk(xk) is to be minimized and fk > 0, the following
transformation allows us to formulate the objective as a linear
function.
hk(xk)=fkyk+ckxk
xk
 0 , yk = 0 or 1
xk  uyk (u is the upper bound of xk)
23
Chapter 7 Integer Programming Models
高等作業研究
KO(i) is the set of arcs originating at node i and KT(i) is the
set of arcs terminating at node i, we have
Minimize z 

f k y k   ck x k

xk 
kA'
C1:
Subject to
kKO ( i )
kA
 xk  bi ,
iS  D  T
kKT ( i )
C2:
xk  uk yk  0,
k  A'
C3:
0  x k  uk ,
k  A'
C4:
yk  0 or 1,
k  A'
24
Chapter 7 Integer Programming Models
高等作業研究
All of the data for the model are included in Figure 7.1.
Constraint C2 represents the implication that if xk is
greater than zero, yk must be 1.
25
Chapter 7 Integer Programming Models
高等作業研究
26
Chapter 7 Integer Programming Models
高等作業研究
FACILITY LOCATION PROBLEM
A logistics company wants to set up a distribution network in
a new region of the country. There are five possible locations for
warehouses and five customer locations that use the
commodities supplied by the warehouses.
Table 7.2 displays the data defining the problem, including unit
shipping costs between potential warehouse sites and customers,
fixed and variable costs for constructing the warehouses,
customer demands, and warehouse capacities.
27
Chapter 7 Integer Programming Models
高等作業研究
The goal is to select warehouse sites and sizes and to establish
a shipping pattern between warehouses and customers that
minimizes total shipping costs as well as the amortized cost
of construction .All demands must be met and the capacity at
each facility must not be exceeded.
28
Chapter 7 Integer Programming Models
高等作業研究
Let us say that m potential sites for warehouses have been
identified and that the locations and demands of the n
customers are known. Let dj be the demand for customer j.
The shipping cost between each potential warehouse site i and
each customer j has been estimated as cij The cost of
establishing a warehouse at location i consists of a fixed cost fi
and a variable cost vi per unit of warehouse capacity.
The maximum capacity at warehouse site i is ui
29
Chapter 7 Integer Programming Models
高等作業研究
Define the following variables.
1 if a warehouse is located at site i
yi  
0 if a warehouse is not located at site i
zi = size of warehouse at location i
xij = amount of product shipped from warehouse i to customer j
The mathematical programming model is as follows.
m
m
m n
i 1
i 1
i 1 j 1
Minimize z   f i yi   vi zi   cij xij
All demands must be met:
m
 xij  d j ,
i 1
n
Supply must not be exceeded:
 xij  zi
i 1
j  1, . . . , n
i  1, . . . ,m
30
Chapter 7 Integer Programming Models
高等作業研究
Shipping from a location implies that the warehouse has
been built:
z i  ui y i ,
i  1, . . . , m
xij  0,
i  1, . . . , m, j  1, . . . , n
Nonnegative size:
zi  0,
i  1, . . . , m
Integrality:
yi  0 or 1,
i  1, . . . , m
Nonnegative shipments:
31
Chapter 7 Integer Programming Models
高等作業研究
32
Chapter 7 Integer Programming Models
高等作業研究
33
Chapter 7 Integer Programming Models
高等作業研究
Uncapacitated Facility Location Problem
It is assumed that there is no limit on the size of the
warehouses. Although the same mathematical programming
model applies with ui , set at an arbitrarily large value, we
present a slightly different formulation that allows for a more
efficient solution technique.
Let
1 if warehouse i is built
yi  
0 otherwise
xij = proportion of demand j satisfied by warehouse i
34
Chapter 7 Integer Programming Models
高等作業研究
Because capacity is unlimited, it can be shown that it is
optimal to meet the demand of each customer from a single
warehouse. As such, the unit transportation cost and the
variable facility cost can be combined with the demand to
obtain the cost coefficient associated with the new variable xij.
This is the cost of supplying the entire demand of customer j
from warehouse i.
cij  (vi  cij )d j
35
Chapter 7 Integer Programming Models
高等作業研究
The new model is as follows.
m
m
n
i 1
i 1 j 1
z   f i yi   cij xij
Minimize
m
All demands must be met:
 xij  1,
j  1, . . . ,n
i 1
Shipping from a location implies that the warehouse has been built
n
x
j 1
ij
 nyi ,
i  1, . . . ,m
Simple bounds:
0  xij  1,
i  1, . . . , m ; j  1, . . . , n
Integrality:
yi = 0 or 1, i = 1, . . . , m
36
Chapter 7 Integer Programming Models
高等作業研究
For the second constraint, it is necessary to multiply the yi
variable on the RHS by n to allow for the extreme case in which
all customers are serviced by warehouse i.
In an alternative formulation, these m implication constraints
representing the potential warehouse sites are replaced by mn
implication constraints each representing the relation between
an individual transportation link and a site:
xij  yi , i=1,...,m ; j=1,....n
37
Chapter 7 Integer Programming Models
高等作業研究
Although this is inefficient from a modeling point of view
because we have increased the number of constraints by a
factor of n, IP algorithms may now be able to find solutions
more quickly.
This increase in efficiency results from the fact that if we
relax the integrality requirement on all yi, the feasible region
associated with the expanded model is much tighter than that
of the original.
38
Chapter 7 Integer Programming Models
高等作業研究
Covering Problem
Consider a microelectronics company that would like to
manufacture six new products. Initial cost estimates indicate that
the equipment needed to make any of the products is very
expensive, and that to make each product individually would
probably require too much investment. It is possible, however, to
produce composite devices that through different interconnections
can perform the functions of two or more of the products.
In fact, a very complex device can be constructed that would have
the same functionality as all six products, but it would require the
use of unproven technology and so has been ruled out.
39
Chapter 7 Integer Programming Models
高等作業研究
After studying the design and manufacturing issues, the
company's engineers have come up with 14 options, each
performing a subset of functions, for management to consider.
The first six options are the products themselves.
To define the problem mathematically, let cj be the equipment
cost for device j and let the column vector Aj represent the set of
functions that the device performs. For instance, the vector A14
= (1, 0,0,1,1,0)T indicates that device 14 can be used for
products 1,4, and 5.
The problem is to find the set of devices with the minimum total
equipment cost that can perform the functions of all six products.
40
Chapter 7 Integer Programming Models
高等作業研究
For convenience, Figure 7.6 shows the 14 vectors
A 1, A2,..., A14 arrayed in a 6×14 matrix in which each
row corresponds to a particular function.
41
Chapter 7 Integer Programming Models
高等作業研究
42
Chapter 7 Integer Programming Models
高等作業研究
Assume that there are, in general, n devices or options, and let
1
xj  
0
if device j is selected for manufacture
otherwise
For x  n , the model is
Minimize cx
subject to Ax  e
xj = 0 or l, j =1,..., n
where e = (1...., 1)T is an n–dimensional vector of 1's.
43
Chapter 7 Integer Programming Models
高等作業研究
We must select devices to cover all functions. The ith row of A
identifies the set of devices that includes the ith function. The
corresponding constraint ensures that at least one of the devices
selected will perform the function.
In the optimal solution for this example, x5= x7= x13= 1, and
all other variables are zero, with cost z = 62. Each function is
covered by this solution, and function 2 is covered twice.
44
Chapter 7 Integer Programming Models
高等作業研究
Partitioning Model
If we now add the restriction that each function must be included
once and only once in the selected devices , the partitioning problem
results. The general formulation is as follows.
Minimize cx
subject to Ax = e
xj = 0 or l, j =1,..., n
For this problem, the subsets cannot overlap, and thus the solution
obtained for the covering model is not feasible because function 2 is
covered twice. Solving this problem, we find that x1=x3= x5= x13=
1 and that all other variables are zero, with cost z = 63.
45
Chapter 7 Integer Programming Models
高等作業研究
Traveling Salesman Problem
Starting at an arbitrary location, we would like to find a
tour that visits each node exactly once and returns to the
original location. The goal is to minimize the sum of the
lengths of the selected arcs.
Let n be the number of nodes in the network and let cij be
the length of the arc passing from i to j. When it is infeasible
to go from i to j either the coefficient cij is set to an
arbitrarily large number or the corresponding variable is
omitted from the formulation.
46
Chapter 7 Integer Programming Models
高等作業研究
The matrix shown in Figure 7-7 gives the distance between each
pair of nodes. The dashes along the diagonal rule out self-loops.
Also, the data imply an asymmetric problem structure, because the
distance from node i to node j is generally not equal to the distance
from node j to node i.
47
Chapter 7 Integer Programming Models
高等作業研究
48
Chapter 7 Integer Programming Models
高等作業研究
A subtour is a sequence of unique nodes that starts and ends
at the same location but visits only a subset of the n nodes. A
solution containing subtours is not feasible.
Define the following decision variables:
1
xij  
0
if the arc from i to j is selected
otherwise
for all i  j  1, ,n
49
Chapter 7 Integer Programming Models
高等作業研究
When i =j, xij does not exist so it is not included in the model.
We now give the mathematical programming formulation of the
asymmetric TSP.
n
Tour length:
Cl:
Minimize z =
n
 c x
i 1 j 1
ij ij
n
Exactly one successor for each node:  xij  1, i  1 , . . ., n
j 1
n
C2:
Exactly one predecessor for each node:  xij  1,
j  1 , . . ., n
i 1
C3:
Subtour elimination:
C4: Integrality.
 x
iS jS
ij
 S  1, S  N , 2  S  n
2
xij = 0 or l, i≠j = l , . . ., n
50
Chapter 7 Integer Programming Models
高等作業研究
Constraint C3 prevents formation of subtours or cycles of
size less than n. It is based on the observation that any subtour
constructed from the nodes in a subset S must have exactly S
arcs.
A major difficulty in solving a TSP is dealing with the
subtour elimination constraints, of which there are 2n–1 – n –1.
The second difficulty in solving a TSP is the loss of the
integrality property commonly associated with network flow
problems. The subtour elimination constraints do not admit a
total unimodular structure.
51
Chapter 7 Integer Programming Models
高等作業研究
Returning now to the six-node example, if one relaxes the
subtour elimination constraints, the assignment problem (AP)
results, which automatically has integer solutions. Solving the AP
relaxation, we obtain the solution {(1, 4), (4, 2), (2, 1), (3, 5), (5,
6), (6,3)}. The corresponding objective function value z = 54
provides a lower bound on the length of me optimal TSP tour.
This solution is not feasible, because it contains two
subtours:(1,4)→(4,2)→(2,1) and (3,5)→(5,6)→(6,3).
52
Chapter 7 Integer Programming Models
高等作業研究
To eliminate the first subtour associated with S = {1, 2, 4},
we add the constraint x12 + x21 + x14 + x41 + x24+ x42 ≦ 2 to
the relaxed formulation. This constraint indirectly eliminates
the second subtour associated with the subset S = (3, 5,6) as
well as the subtour in the opposite direction:
(1,2)→(2,4)→(4,1).
Solving the new problem, we obtain the solution {(1,4), (4,3),
(3,5), (5,6), (6,2), (2,1)}, with z = 63. This solution contains
no subtours and so is optimal (see Figure 7.9).
53
Chapter 7 Integer Programming Models
高等作業研究
The idea of solving a relaxed version of the problem and then
adding constraints sequentially to remove subtours is the
strategy followed by the most sophisticated algorithms. The
basic approach is simply to try to solve the full model using
implicit enumeration (branch and bound).
The combination of implicit enumeration and the sequential
addition of constraints is called branch and cut.
54
Chapter 7 Integer Programming Models
高等作業研究
Homework
Solve the following TSP with a branch and cut method.
1
2
3
4
5
1
-
17
10
15
17
2
18
-
6
10
20
3
12
5
-
14
19
4
12
11
15
-
7
5
16
21
18
6
-
55
Chapter 7 Integer Programming Models
高等作業研究
Directed Minimal Spanning Tree Problem
Given a directed graph G = (N, A) with node set N and arc
set A, a tree is a subgraph G' = (N, A') that has no cycles and
is connected (contains a directed path from the root node to
all other nodes in N ). The directed minimal spanning tree
(MST) problem is to find a tree rooted at, say, node 1 with a
directed path to every other node. The goal is to minimize the
sum of the arc lengths used in the tree.
The model for this problem is similar to that of the TSP
except now one or more arcs may leave node 1; however,
there is no requirement that any arcs leave nodes 2,..., n.
56
Chapter 7 Integer Programming Models
高等作業研究
Mathematical programming formulation is
n
Tree length:
Minimize z =
n
 c x
ij ij
i 1 j 1
n
At least one arc must leave root node 1:
x
j 1
1
1j
n
One predecessor for all other nodes :
x
TSP subtour elimination constraints :
 x
Integrality.
i 1
iS jS
ij
 1,
ij
j  2 , . . ., n
 S  1, S  N , 2  S  n
2
xij = 0 or l, i≠j = l , . . ., n
57
Chapter 7 Integer Programming Models
高等作業研究
Again we solve the relaxation of the problem obtained by
removing the subtour elimination constraints. The solution to
this problem is {(1,4), (3,6), (3,5), (6,2), (6,3)}, with z = 31.
It contains the cycle (6,3)→(3,6),so we add the constraint x63+
x36  1 and resolve.
At the next two iterations, we add
x56+x65  1 and x35+ x53+ x56+ x65+ x63+ x36  2, respectively,
to eliminate the corresponding cycles.
The solution at this step is {(1,6), (6,2), (6,3). (6,5), (2,4)},
with z = 42, and is optimal .
58
Chapter 7 Integer Programming Models
高等作業研究
Shortest Path Tree Problem
Given a directed graph, we wish to find a tree rooted at, say,
node 1 with a path leading to every other node. The goal is to
minimize the sum of the individual path lengths.
To develop a mathematical programming formulation for the
problem, we must define the variables in a way that allows the
arcs to be used multiple times. Accordingly,
let
xij = number of paths using the arc from i to j
59
Chapter 7 Integer Programming Models
高等作業研究
The model for the shortest path tree problem is as follows.
Length of the n–1 paths :
Minimize z =
n
n
 c x
i 1 j 1
n
Cl: At node 1, supply = n –1:
C2:
Conservation of flow:
C3:
Nonnegativity:
x
j 1
1j
ij ij
 n 1
n
n
j 1
j 1
 xij   x ji  1,
xij
i  2 , . . ., n
 0 , i≠j = l , . . ., n
60
Chapter 7 Integer Programming Models
高等作業研究
Constraint Cl requires that exactly n –1 units of flow leave
the root node 1, thus establishing n – 1 paths. For every other
node, the amount of flow entering that node must be one unit
greater than the amount leaving. This is guaranteed by
Constraint C2.
Note that we have not required the variables to have integer
values in Constraint C3. Since this is a pure network flow
problem, the constraint matrix is totally unimodular. The
solution will automatically be integer valued.
61
Chapter 7 Integer Programming Models
高等作業研究
The Cutting Stock Problem
A paper company sells rolls of paper of fixed length in five
standard widths; 5,8,12,15, and 17 feet. Its manufacturing
process produces 25-foot-wide rolls only, so all orders must be
cut from stock of this size.
Demands for the 5-, 8-, 12-, 15-, and 17-foot rolls are
40,35,30,25, and 20, respectively.
The problem is to cut the manufactured rolls in a fashion
that minimizes the total number required.
Manufactured rolls can be cut in 11 different patterns, as
shown in Figure 7.14. Some patterns result in excess paper
(shown in black) that must be discarded. .
62
Chapter 7 Integer Programming Models
高等作業研究
Simplify the situation somewhat, no pattern is included hat
has an excess as great as the smallest standard width (5 feet).
Also, each roll can be cut in only one pattern.
Because each pattern is cut from a 25-foot-wide roll, we can
assign a unit cost to each pattern. The goal is to select an
integral number of rolls to be cut in each pattern so that the total
cost is minimized and the demand satisfied.
63
Chapter 7 Integer Programming Models
高等作業研究
64
Chapter 7 Integer Programming Models
高等作業研究
To formulate the model,
let xj = number of rolls cut in pattern j
Minimize
z
 x2
x1
 x3
 x4
 x5
 x6
 x7
 x8
 x9  x10  x11
subject to
 2 x4
x2
 x6
 2x7
 x9  3x10  5 x11  40
(Demend for 5-foot rolls)
 x3
x1
 x6
 3 x8
 2x9  x10
 35
(Demend for 8-foot rolls)
 2 x5
 x6
 x7
 30
(Demend for 12-foot rolls)
 x3
 x4
 25
(Demend for 15-foot rolls)
x1
 x2
 20
(Demend for 17-foot rolls)
x j  0 and integer, j  1,....,11
65
Chapter 7 Integer Programming Models
高等作業研究
Three optimal solutions are shown in Table 7.3, with the total
number of rolls cut being equal to 64 in each case. Only the
second solution satisfies the demand exactly.
66
Chapter 7 Integer Programming Models
高等作業研究
Production Scheduling
You are given the demands for two products A and B over a
5-day period. Both products are manufactured on the same
machine, but on any given day the machine can be used for
only one product because of the extensive changeover time.
Job is to establish a production schedule for the machine that
shows which product, and the amount of that product, that
should be manufactured on each day. The schedule must ensure
that all demands are met without shortages.
67
Chapter 7 Integer Programming Models
高等作業研究
The machine is set up for production each morning. Let dAt
and dBt be the respective product demands, with t ranging from
1 to 5. The corresponding setup costs are $100 for product A
and $50 for product B.
For each of the 5 days, you are to determine if product A,
product B, or neither is to be manufactured.
When product A is being manufactured, the machine can
produce at most 10 units per day, when product B is being
manufactured, the machine can produce at most 20 units per
day. On any given day, you can produce more than is needed
and place the excess in inventory.
68
Chapter 7 Integer Programming Models
高等作業研究
The cost of storing product A is $2 unit per day , the cost of
storing product B is $3 per unit per day. There are 10 units of
each product in inventory.
At the end of the 5–day planning period, inventories are to
be zero. For convenience, assume that all additions to and
withdrawals from inventory occur at the beginning of each day.
69
Chapter 7 Integer Programming Models
高等作業研究
Definition of Variables
Real variables:
At = quantity of product A produced on day t
Bt = quantity of product B produced on day t
It = inventory of product A at the end of day t
Jt= inventory of product B at the end of day t
Binary variables:
xt = decision to produce product A on day t
yt = decision to produce product B on day t
70
Chapter 7 Integer Programming Models
高等作業研究
Objective Function
5
Minimize z =  (100 xt  50 yt  2 I t  3J t )
t 1
Constraints
Conservation of inventory (t=l,...,5):
Cl:
At  I t  I t 1  d At
Bt  J t  J t 1  d Bt
Initial and final inventories:
C2:
I0=10 , J0=10 , I5=0 , J5=0
71
Chapter 7 Integer Programming Models
高等作業研究
Capacity implications (t = 1,..., 5):
C3:
At  10 x t
Bt  20 yt
At most one product on any day (t = 1,.... 5):
C4:
xt  y t  1
Integrality and nonnegativity (t = 1,..., 5):
C5:
xt , yt  0 or 1; At , Bt , I t , J t  0
72
Chapter 7 Integer Programming Models
高等作業研究
Production Scheduling with Continued Setup
We now modify the preceding example so that the setup for a
particular product can be carried over from one day to the next.
In this situation, if the machine is set up for product A on day t
at a cost of $ 100, it is available to manufacture product A on
any number of consecutive days with no additional setup cost.
This feature can be easily accommodated in the existing model
by noting that the expression
xt (1  xt 1 )
has the value 1 only if xt= 1 and xt–1=0. This will occur
whenever production of product A starts on day t.
73
Chapter 7 Integer Programming Models
高等作業研究
The model can be modified by inserting this factor (and a similar
one for product B) into the objective function, yielding
5
Minimize z   [100 xt (1  xt 1 )  50 y t (1  y t 1 )  2 I t  3J t ]
t 1
74
Chapter 7 Integer Programming Models
高等作業研究
Unfortunately, the objective now has nonlinear terms that are
simple in appearance but are not allowed in linear–integer
programming models. An acceptable alternative is to introduce
two binary variables ut and vt to replace the multiplicative terms
in the objective function.
Let
1 if production begins on product A on day t
ut  
0 otherwise
1 if production begins on product B on day t
vt  
0 otherwise
We must now add constraints that determine the values of ut,
and vt in terms of xt and yt
75
Chapter 7 Integer Programming Models
高等作業研究
Constraints defining production initiation (t = 1,.... 5):
xt  (1  xt 1 )  1  ut
C6:
yt  (1  yt 1 )  1  vt
The new objective function is
5
Minimize z   [100ut  50vt  2 I t  3J t ]
t 1
which now has a linear form.
76
Chapter 7 Integer Programming Models
高等作業研究
The primary reason why this transformation works is that we are
minimizing cost and so there is no incentive for ut or vt to be
positive unless there is a desire to begin manufacturing the
respective products on day t.
77
Chapter 7 Integer Programming Models
高等作業研究
Days-Off Scheduling
The most common example is the (5,7)-cyclic staffing problem,
in which each employee works 5 days per week given two
consecutive days off. To formulate the model for this problem,
let
xj = number of employees assigned to days-off pattern j
cj = weekly cost of days-off pattern j per employee
ri = number of employees required on day i
78
Chapter 7 Integer Programming Models
高等作業研究
In the objective function, the coefficient ci can account for such
factors as premium pay for weekend assignments, different pay
rates for different labor categories, assuming a more elaborate
model that included, say, full-time and part-time employees.
7
Minimize z   c j x j
j 1
Subject to
 7

  x j   xi  xi 1  ri , i  1...


 j 1 
x j  0 and integer j  1,..., 7 where x0  x7
79
Chapter 7 Integer Programming Models
高等作業研究
or
Minimize z = cx
0
subject to 0

1

1
1

1
1
1 1 1 1 1 0
0 1 1 1 1 1

0 0 1 1 1 1

1 0 0 1 1 1 x  r
1 1 0 0 1 1

1 1 1 0 0 1
1 1 1 1 0 0
x  0 and integer
80
Chapter 7 Integer Programming Models
高等作業研究
Each column of the A matrix represents a feasible days-off
pattern.
Although the A matrix is not totally unimodular, it does have a
special structure called the circular property. In particular, a 0-1
vector is said to be circular if its 1's occur consecutively, where
the first and last entries are considered to be adjacent. Veinott and
Wagner [1962] recognized that a related ILP with consecutive 1's
could be transformed into network flow problems. Building on
that work, Bartholdi, Orlin, and Ratliff [1980] transformed the (k,
m)-cyclic staffing ILP into a bounded series of network flow
problems.
81
Chapter 7 Integer Programming Models
高等作業研究
In addition, they provided an alternative solution technique to
the original problem based on LP rounding. The steps of this
technique are as follows.
1. Ignoring the integrality restrictions in the days-off ILP,
solve the LP relaxation to obtain the solution x1 ,…, x 7
If these values are all integer, this is the optimal
solution to the ILP; if not, go to Step 2.
82
Chapter 7 Integer Programming Models
高等作業研究
2. Form two linear programs LP1 and LP2 from the
relaxation in Step 1 by adding, respectively, the
constraints x1+ x2+…..+ x7 = x1  .....  x7  and x1+
x2+…..+ x7 = x1  .....  x7  where  y  is the smallest
integer greater than or equal to y and  y  is the largest
integer less than or equal to y. LP1 is always feasible,
but it is possible that LP2 is infeasible. In either case,
it can be shown that if an optimal solution exists, then
an integral optimal solution exists, so the better of the
two solves the days-off ILP.
83
Chapter 7 Integer Programming Models
高等作業研究
Homework
Solve the previous days-off scheduling example with
[c1, c2, c3, c4, c5, c6, c7]=[8, 10, 13, 15, 14, 12, 9] and
[r1, r2, r3, r4, r5, r6, r7]=[30, 60, 65, 70, 60, 55, 40].
84
Chapter 7 Integer Programming Models
高等作業研究
Assembly Line Balancing
A wide range of products are assembled on fixed-paced flow
lines consisting of a collection of workstations. One or more
operations are performed at each station, with some restrictions on
the order, these are called precedence relations. There is also a limit
on the amount time a product can spend at any particular
workstation. This value is known as the cycle time and is assumed
to be fixed.
Consider an example of a product whose manufacture requires
five operations. The decisions involve allocating each operation to
a particular workstation so that the number of stations is minimized.
Table 7.4 gives the precedence relations and the time needed to
complete each operation.
85
Chapter 7 Integer Programming Models
高等作業研究
86
Chapter 7 Integer Programming Models
高等作業研究
Logically, operation i is either performed or not performed at
station j.
1
Let xij  
0
if operation i is done at station j
otherwise
Suppose that the maximum time available at each workstation is
12 minutes. Along with the data in Table 7.4, this implies that at
most four stations are needed. Hence, we have the following four
constraints.
5
px
i 1
i
ij
 12 ,
j  1, . . .,4
87
Chapter 7 Integer Programming Models
高等作業研究
The total time taken for all operations assigned to a station must
be no more than 12 minutes.
Expanding these inequalities yields
6 x11  5x21  7 x31  6 x41  5x51  12
6 x12  5x22  7 x32  6 x42  5x52  12
6 x13  5x23  7 x33  6 x43  5x53  12
6 x14  5x24  7 x34  6 x44  5x54  12
88
Chapter 7 Integer Programming Models
高等作業研究
By saying that operation 3 must be done before operation 4, we
mean that the former must be performed either at the same
workstation as the latter or at a prior workstation. In mathematical
k
terms, operation i is done at or before station k if  j 1 xij  1 and is
k
k
done after station k if  j1 xij  0 . If x 4 k   j 1 x3 j then operation
4 cannot be done at station k unless operation 3 has been done,
k
because x4k = 1 only if  j 1 x3 j  1 . The precedence relations must
hold at all stations, so
x4 k   j 1 x3 j , k  1, . . .,4
k
89
Chapter 7 Integer Programming Models
高等作業研究
If neither operation is done at or prior to station k, this expression
holds trivially (i.e.,0  0); it also holds if both operations are done at
station k (i.e.,1  1).
One set of constraints is required for each precedence relation For
job 5, the constraints are

  x2 j 
j 1

 k  1,...,4
k
  x4 j 

j 1
k
x5k
x5k
90
Chapter 7 Integer Programming Models
高等作業研究
To ensure that each operation is performed once and only once,
we require
4
x
j 1
ij
 1, i  1,....,5
The objective is to find the minimum number of workstations
needed to assemble the product. This can be achieved by assigning a
smaller "cost" to operation i performed at station 1 than for
operation i performed at station 2, and so on. By minimizing these
costs, we force each operation to be allocated to the earliest possible
workstation. One way to specify the objective function coefficients
to obtain the desired result is to let cij=j for all i.
91
Chapter 7 Integer Programming Models
高等作業研究
Consequently we have
5
5
5
5
i 1
i 1
i 1
i 1
Minimize z   xi1  2 xi 2  3 xi 3  4 xi 4
Preceding equations together with the nonnegativity and
integrality conditions on the variables
xij  0 and integer for all i and j
make up the integer program for this problem. Note that we do not
need to impose an upper bound of 1 on each xij, because the last
constraint does this implicitly.
92
Chapter 7 Integer Programming Models
高等作業研究
5
5
5
5
i 1
i 1
i 1
i 1
Minimize z   xi1  2 xi 2  3 xi 3  4 xi 4
s.t.
5
px
i
i 1
ij
 12 ,
j  1, . . .,4
x4 k   j 1 x3 j , k  1, . . .,4
k

  x2 j 
j 1

 k  1,...,4
k
  x4 j 

j 1
k
x5k
x5k
4
x
j 1
ij
 1, i  1,....,5
xij  0 and integer for all i and j
93
Chapter 7 Integer Programming Models

Download Report