8jJUrTR5xXP3Vw
CO 250 Spring 2023: Assignment 3 solutions
A3-1. (a) Variables: For each j ∈ B, define xj to be the binary variable representing
xj =
{
1 iFjord accepts buyer j’s bid
0 otherwise
.
Objective function: We want to maximize the total bids received. So the objective
function is
max
m∑
j=1
bjxj
Constraints: We first ensure that our variables are binary:
0 ≤ xj ≤ 1, xj ∈ Z
For each item i ∈ I, we need to ensure that no more than si is sold. We can calculate
the total number of item i sold by multiplying what buyer j wants vji by xj, then sum
over all buyers. This gives us the constraints
m∑
j=1
vjixj ≤ si ∀i ∈ I
Full IP:
max
m∑
j=1
bjxj
s.t.
m∑
j=1
vjixj ≤ si ∀i ∈ I
0 ≤ xj ≤ 1, xj ∈ Z ∀j ∈ B
(b) Define variables t1, t2 to represent the total number of buyers in B1, B2 respectively
whose bids are accepted by iFjord. Then we add the constraints
t1 =
∑
j∈B1
xj, t2 =
∑
j∈B2
xj, t1, t2 ∈ Z.
Define binary variables y1, y2 to represent
yi =
{
1 iFjord accepts bids from at least 2 buyers of Bi
0 otherwise
, i = 1, 2.
We need binary constraints
0 ≤ y1, y2 ≤ 1, y1, y2 ∈ Z.
8jJUrTR5xXP3Vw
To implement the definition of yi, consider the constraints
2yi ≤ ti, ti ≤ 1 +myi, i = 1, 2
We see that when yi = 1, we get 2 ≤ ti ≤ 1 +m, meaning the number of accepted bids
from Bi is at least 2, and no more than 1 + m (as there are up to m buyers). When
yi = 0, we get 0 ≤ ti ≤ 1, meaning less than 2 bids are accepted.
We now ensure that whenever one group has at least 2 bids accepted, the other group
has 0. This can be implemented using these constraints:
t1 ≤ m(1− y2), t2 ≤ m(1− y1).
We see that when y1 = 1, we have t2 ≤ 0, meaning when group B1 has two bids accepted,
group B2 has 0 bids accepted. When y1 = 0, we have t2 ≤ m, which does not limit the
value of t2. A similar argument follows for y2.
8jJUrTR5xXP3Vw
A3-2. Variables: For each toy j ∈ T , define xj to be the total number of units of toy j that are
produced.
For each i ∈ {1, 2}, j ∈ T, k ∈ H, we define the binary variable yijk to represent
yijk =
{
1 machine Mi processes toy j during hour k
0 otherwise
.
We also define binary variables zijk to represent
zijk =
{
1 machine Mi starts a new shift on toy j during hour k
0 otherwise
.
Constants: For convenience, we will introduce constants yij0 = 0 for all i ∈ {1, 2}, j ∈ T .
This represents the machine does not operate during hour 0.
Objective function: We want to maximize the total value of the toys produced. So the
objective function is
max
∑
i∈T
pjxj
Constraints: We first enforce non-negativity, binary and integral constraints.
xj ≥ 0, xj ∈ Z, yijk, zijk ∈ {0, 1} ∀i ∈ {1, 2}, j ∈ T, k ∈ H.
Each machine can process at most one toy during each hour. So∑
j∈T
yijk ≤ 1 ∀i ∈ {1, 2}, k ∈ H.
The two machines cannot process the same type of toy during the same hour. So
y1jk + y2jk ≤ 1 ∀j ∈ T, k ∈ H.
We now implement the definition of zijk using constraints. We note that machine Mi starts
a new shift of toy j at hour k if yijk = 1 and yij(k−1) = 0 (in other words, Mi is working on
toy j during hour k, but it is not working on toy j during hour k − 1). So the definition of
zijk is equivalent to
zijk =
{
1 yijk − yij(k−1) = 1
0 yijk − yij(k−1) = 0,−1 .
We claim that this can be implemented with the following constraints:
zijk ≥ yijk − yij(k−1), zijk ≤ 0.5(1 + yijk − yij(k−1)), ∀i ∈ {1, 2}, j ∈ T, k ∈ H.
(Note that this is why we need the constants yij0.) We can verify the correctness of these
constraints:
• When yijk − yij(k−1) = 1, we get 1 ≤ zijk ≤ 1, meaning zijk = 1.
8jJUrTR5xXP3Vw
• When yijk − yij(k−1) = 0, we get 0 ≤ zijk ≤ 0.5, meaning zijk = 0.
• When yijk − yij(k−1) = −1, we get −1 ≤ zijk ≤ 0, meaning zijk = 0.
Finally, we need to deal with the number of units of each toy produced xj. There is a limit
of cj units of materials for toy j, so
xj ≤ cj ∀j ∈ T.
For machine M1, we want xj to be at most the number of units of toy j that is processed, so
xj ≤ αj
∑
k∈H
y1jk − 0.5αj
∑
k∈H
zijk ∀j ∈ T.
(In other words, we calculate how many hours it worked on toy j and multiply by the rate αj.
But the hours during which the machine starts a new shift has half the rate, so we subtract
0.5αj from those hours.)
We can write a similar constraint for machine M2.
xj ≤ βj
∑
k∈H
y2jk − 0.5βj
∑
k∈H
z2jk ∀j ∈ T.
Since our objective function is maximizing each xj, we see that xj will equal to the minimum
of the three values (materials available, units processed by machine M1, and units processed
by machine M2).
Full IP:
max
∑
i∈T
pjxj
s.t. xj ≥ 0, xj ∈ Z, yijk, zijk ∈ {0, 1} ∀i ∈ {1, 2}, j ∈ T, k ∈ H∑
j∈T
yijk ≤ 1 ∀i ∈ {1, 2}, k ∈ H
y1jk + y2jk ≤ 1 ∀j ∈ T, k ∈ H
zijk ≥ yijk − yij(k−1), zijk ≤ 0.5(1 + yijk − yij(k−1)), ∀i ∈ {1, 2}, j ∈ T, k ∈ H
xj ≤ cj ∀j ∈ T
xj ≤ αj
∑
k∈H
y1jk − 0.5αj
∑
k∈H
zijk ∀j ∈ T
xj ≤ βj
∑
k∈H
y2jk − 0.5βj
∑
k∈H
z2jk ∀j ∈ T
8jJUrTR5xXP3Vw
A3-3. (a) The objective function is
min 10xsa+3xsb+5xse+6xab+3xad+9xat+xbe+xcd+4xce+7xcf +5xdt+12xef +xft
or
min (10, 3, 5, 6, 3, 9, 1, 1, 4, 7, 5, 12, 1)x
(b) The cut δ({s, a, b}) consists of 4 edges (shown on the left below. The corresponding
constraint is
xse + xad + xat + xbe ≥ 1
or
(0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0)x ≥ 1.
The cut δ({s, c, d, f}) consists of 8 edges (shown on the right below. The corresponding
constraint is
xsa + xsb + xse + xad + xce + xdt + xef + xft ≥ 1
or
(1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1)x ≥ 1.
s a
b
c d
e f t
10
3 6
5
1
4
1
5
7
12 1
3
9
δ({s, a, b})
s a
b
c d
e f t
10
3 6
5
1
4
1
5
7
12 1
3
9
δ({s, c, d, f})
(c) There should be 26 = 64 constraints in total. An s, t-cut δ(S) is generated by the set
S where s ∈ S and t ̸∈ S. For the remaining 6 vertices, each of them can be either
inside S or outside S. So there are 2 ways to choose where each vertex goes, and with 6
vertices, there are then 26 ways to pick S. Hence there are 26 constraints, one for each
of the 26 s, t-cuts.
(d) i. This is a feasible solution, as the edges with value 1 form an s, t-path (sb, ab, ad, cd, cf, ft).
And any s, t-cut uses at least one edge of any s, t-cut. Hence the constraints are
satisfied.
ii. This is not a feasible solution. Consider the cut δ({s, a, b}). As illustrated in part
(b), there are 4 edges in this cut, and all of their corresponding variables have value
0. Hence the constraint corresponding to this cut is not satisfied.
iii. This is a feasible solution. We see that every cut contains at least one edge, and
every edge has value at least 1. So all the cut constraints are satisfied.
8jJUrTR5xXP3Vw
(e) An optimal solution is
(0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0)T .
It is shown as values in boxes below.
s a
b
c d
e f t
10
3 6
5
1
4
1
5
7
12 1
3
9
0
0
0
0
0
0
0
0
1
1 1
1
1
It is difficult to justify optimality as there are a lot of feasible solutions to check, and it
is hard to be sure that all of them have been checked.