Question 1 – Modelling 0/1 problems 15 points

There are seven important shopping regions in the Hyderabad area: Ameerpet,
Begumpet, Charminar, Dilsukhnagar, Erragadda, Falaknuma, and Gachibowli (A, B, C, D,
E, F, and G for short). The Greater Hyderabad Muncipal Corporation (GHMC) wants to
achieve the goal that every person living in any one of these regions has to be within 10km
of a “lifestyle mall”. You have been brought in as an consultant to decide where to build
these malls. There are proposals to build a mall in each of the seven regions. The distances
between the various regions and costs of building a mall in each region are given in Table
1.1 below:

Distances between different regions and cost of building malls in each region

Regions A B C D E F G Costs

A 0.0 6.1 15.2 17.0 16.8 8.4 16.6 10

B 6.1 0.0 7.6 16.0 11.3 2.2 11.9 6

C 15.2 7.6 0.0 22.0 17.3 10.2 16.7 7

D 17.0 16.0 22.0 0.0 12.1 14.8 7.2 8

E 16.8 11.3 17.3 12.1 0.0 9.4 2.9 13

F 8.4 2.2 10.2 14.8 9.4 0.0 9.2 9

G 16.6 11.9 16.7 7.2 2.9 9.2 0.0 8

(a) Formulate an integer program that will determine the locations to build lifestyle
malls at a minimum cost subject to the constraint that each district is within 10km
of a mall. Clearly define decision variable, objective function and constraints.
(8 points)

Decision variable:
Define Xi = {1 if mall is built in region i and 0 otherwise} i = A, B, C, D, E, F, G

Objective function: Minimise costs subject to building malls

Minimise Z = 10Xa + 6Xb + 7Xc+8Xd +13Xe +9Xf + 8 Xg

S.T
Constraints, check for each city, then add the constraint

For person in A, you need malls at either A, B, F i.e. Xa+Xb+Xf >=1

For B, you need malls at either A, B, C, F i.e. Xa+Xb+Xc+Xf >=1
For C, you need malls at either B, C, i.e. Xb+Xc >=1
For D, you need malls at either D,G i.e. Xd+Xg >=1
 For E, you need malls at either E,F,G i.e Xe+Xf+Xg >=1
For F, you need malls at either A,B, E,F,G i.e. Xa+Xb+Xe+Xf+Xg >=1
For G, you need malls at either D, E,F,G i.e. Xd+Xe+Xf+Xg > =1

(b) The MLAs of Begumpet and Gachibowli are at loggerheads, and so, the MLA of
Gachibowli has said that if a mall is located in Begumpet then a mall will not be
located in Gachibowli. Modify your model to accommodate this. (2 points)

If Xb =1 , then Xg = 0
Xb+Xg<=1

(c) The MLAs of Begumpet and Gachibowli have made up with each other; so, the
constraint of part (c) does not hold anymore. Now suppose that if a mall is located
in Begumpet or Gachibowli (or both), then a mall has to be located in one of the
other regions. Modify your model to accommodate this. (3 points)

If Xb + Xg >= 1, then Xa + Xc + Xd + Xe + Xf >=1

If Xb + Xg > = 1 implies Delta = 1

M = Higher value of (Xb+Xg-1) = 1, Epsilon = 1

Xb + Xg – (1+1)delta < = 0 Therefore delta > = 0.5 (Xb+Xg)

Now if Delta = 1 implies Xa+Xc+Xd+Xe+Xf>=1

Small m = lower value of (Xa+Xc+Xd+Xe+Xf-1) = -1

Xa+Xc+Xd+Xe+Xf > = 1 + (-1) ( 1-delta)

Xa+Xc+Xd+Xe+Xf > = delta

Xa+Xc+Xd+Xe+Xf > = 0.5 (Xb+Xg)

(d) It is now learnt that the MLAs of Begumpet and Gachibowli reconciled via
negotiations with the MLA of Erragadda. So, now if a mall is located in Begumpet
or Gachibowli (or both), then a mall has to be located in Erragadda. Accommodate
this constraint. (2 points)

If Xb + Xg >= 1, then Xe =1

Xe > = 0.5 (Xb+Xg)

Question 2 – Modelling 0-1 problems (25 points)

Consider a General Assignment Problem (GAP) problem, where a set of 𝑁 ≡ {1, … , 6} jobs
are to be assigned to a set of 𝑀 ≡ {1, … ,5} machines. The 6 jobs require 7, 5, 9, 8, 6, 4 units
of work respectively, and the 5 machines have a capacity of 11, 8, 8, 14, 9 units of work
respectively. Each job must be assigned to exactly one machine, and it is not necessary to
use all the 5 machines.
The cost incurred if job 𝑗 ∈ 𝑁 is scheduled on machine 𝑖 ∈ 𝑀 is given in the table below:

Job 1 Job 2 Job 3 Job 4 Job 5 Job 6

Machine 1 3 7 5 11 9 2
Machine 2 5 8 7 1 8 1
Machine 3 4 4 8 3 7 7
Machine 4 2 3 3 6 3 8
Machine 5 1 6 9 5 4 9

a) Formulate an integer programming model to determine an assignment of jobs to

machines that minimizes the total cost and does not exceed the machine capacities.
Clearly define your decision variables, objective function, and constraints. (10 points)

Decision variable: Xij = {1, if ith machine is assigned to jth job; 0 otherwise}

Objective Function:

Minimize 𝑍 = ∑5𝑖=1 ∑6𝑗=1 𝐶𝑖𝑗 ∗ 𝑋𝑖𝑗 ; costs Cij are given in above table

Constraints:

Capacity constraints:

Mach 1 7X11 + 5X12 + 9X13 + 8 X14 + 6 X15 + 4X16 <= 11

Mach 2 7X21 + 5X22 + 9X23 + 8 X24 + 6 X25 + 4X26 <= 8

Mach 3 7X31 + 5X32 + 9X33 + 8 X34 + 6 X35 + 4X36 <= 8

Mach 4 7X41 + 5X42 + 9X43 + 8 X44 + 6 X45 + 4X46 <= 14

Mach 5 7X51 + 5X52 + 9X53 + 8 X54 + 6 X55 + 4X56 <= 9

Each job for 1 machine:

∑5𝑖=1 𝑋𝑖𝑗 = 1 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑗 = 1,2,3,4,5,6

Non-negative and binary; Xij = {0,1}

b) Now suppose that Job 2 and Job 5 must be scheduled on the same machine. Add
suitable constraint(s) to your formulation in part (a) to model this requirement.
(2 points)

𝑋𝑖2 = 𝑋𝑖5 𝑓𝑜𝑟 𝑖 = 1,2,3,4,5

c) In addition to the assignment costs given above, suppose that a fixed cost is incurred
when machine 𝑖∈𝑀 is operated. The fixed cost of operating a machine for each of these
five machines are given by 25, 30, 24, 19 and 17, respectively. Modify the formulation
in part (a) to incorporate this fixed cost. Define any new variables, if required.
(5 points)

Additional Decision variable:

Yi = {1 if ith machine is used and 0 otherwise}

Objective function:
Minimise 𝑍 = ∑5𝑖=1 ∑6𝑗=1 𝐶𝑖𝑗 ∗ 𝑋𝑖𝑗 + 25𝑌1 + 30𝑌2 + 24𝑌3 + 19𝑌4 + 17𝑌5

Additional Constraints: You need to link Xij and Yi

Linking Constraints: 𝑋𝑖𝑗 ≤ 𝑌𝑖 𝑓𝑜𝑟 𝑖 = 1 𝑡𝑜 5 𝑎𝑛𝑑 𝑗 = 1 𝑡𝑜 6

OR
you can rewrite capacity constraints and Multiply RHS by Yi for each machine e.g.:
Mach 1 7X11 + 5X12 + 9X13 + 8 X14 + 6 X15 + 4X16 <= 11Y1

d) Referring to your formulation in part (c), write an inequality that models the
condition that at most 4 out of the 5 machines can be in operation. (2 points)

𝑌1 + 𝑌2 + 𝑌3 + 𝑌4 + 𝑌5 ≤ 4

e) Referring to your formulation in part (c), write an inequality (or inequalities) that
models the following condition: If Machine 4 is in operation, then at least 20% of its
capacity must be used. (2 points)

Original Maximum capacity constraint of Mach 4

7X41 + 5X42 + 9X43 + 8 X44 + 6 X45 + 4X46 <= 14Y4

{ Y4 is added to RHS based on ans c}

As per new minimum capacity constraint,

7X41 + 5X42 + 9X43 + 8 X44 + 6 X45 + 4X46 >= 0.2*14*Y4 = 2.8Y4

f) Referring to your formulation in part (c), write an inequality (or inequalities) that
models the following condition: If Machine 1 is operated, then at most three of the
machines {2,3,4,5} can be operated. (2 points)

If Y1=1, then Y2+Y3+Y4+Y5<=3

𝑌1 + 𝑌2 + 𝑌3 + 𝑌4 + 𝑌5 ≤ 4

g) Referring to your formulation in part (c), give a constraint to model the following
condition: if at least two out of the three machines 1, 2, and 3, are in operation, then
at least one of the machines 4 or 5 must be in operation. (They don’t necessarily have
to have jobs assigned to them if they are in operation.) (2 points)

If 𝑌1 + 𝑌2 + 𝑌3 ≥ 2, then 𝑌4 + 𝑌5 ≥ 1

If 𝑌1 + 𝑌2 + 𝑌3 ≥ 2 implies Delta = 1

M = Higher value of (Y1 + Y2 + Y3 -2) = 1, Epsilon = 1

𝑌1 + 𝑌2 + 𝑌3 – (1+1)delta < = (2-1) Therefore delta > = 0.5 (𝑌1 + 𝑌2 + 𝑌3 − 1)

Now if Delta = 1 implies 𝑌4 + 𝑌5 >=1

Small m = lower value of (𝑌4 + 𝑌5 -1) = -1

𝑌4 + 𝑌5 >= 1 + (-1) (1-delta)

𝑌4 + 𝑌5 > = delta

𝑌4 + 𝑌5 > = 0.5 (𝑌1 + 𝑌2 + 𝑌3 - 1)

Question 3 – Branch and Bound Problem (15 points)

Consider the following integer programming problem:

Minimize −X1− X3+ X4
Subject to:
−2X1+7X2+ 3X3+X4 ≤ 6
7X1+3X2− 4X3−2X4 ≤1
2X2+ 3X3+6X4 ≥5
−3X1 + 2X3 ≤1
Xi ≥ 0 𝑎𝑛𝑑 integer, 𝑖=1,2,3,4.
You are given a partially completed branch-and-bound tree below, where the labels at
the center of the nodes indicate the order in which the nodes were evaluated, i.e., its LP
relaxation was solved.
The notation 𝑧𝑘=𝑞 indicates that a linear programming relaxation at the node labeled k
was solved and the objective function value is q. The notation 𝑥𝑘= (𝑎, 𝑏, 𝑐, 𝑑) indicates
that the solution to the LP relaxation at node k is given by 𝑥1= 𝑎, 𝑥2= 𝑏, 𝑥3= 𝑐, 𝑥4= 𝑑. An
active node is defined as one that still needs to be explored and cannot be fathomed. At
any stage, the incumbent solution is the best-known integer (feasible) solution to the
problem.
You are required to complete the branch-and-bound tree and determine the optimal
solution to the problem. Towards this end, answer the following questions:

a) What is the current incumbent solution? (1 point)

Current incumbent solution is at node 2 i.e, 𝑥2= (3, 0, 2, 6) and 𝑧2=1

b) What is the best lower bound on the problem at this stage? (1 point)

Best lower bound on the problem is −4.857 at Node 3.

c) What are the active nodes in the branch-and-bound tree at this stage? (1 point)
 Active Nodes are 5,7 and 8.

d) Formulate and use MS Excel Solver to solve the linear programming relaxation at
Node 5. Upload your MS Excel file showing the formulation and calculations.(4 points)

To get LP relaxation at node 5,

We add constraints X1 ≤ 1 and X3 ≤ 3 to the original problem.

Solving this in excel ( You might not have excel; in such cases, you will be given the
solution in separate tree with diff type of questions),
we get: 𝑥5= (1, 0, 2, 0) with 𝑧5=− 3.

e) Based on your solution to part (d), did the incumbent value change? If yes, what is the
new incumbent solution? (1 point)

The incumbent solution gets updated to 𝑥5= (1, 0, 2, 0) with 𝑧5=− 3.

f) What are the active nodes in the branch-and-bound tree at this stage? (1 point)

Active nodes in the tree are Node 7 and Node 8.

g) From the solution shown at Node 6, select an appropriate branching variable and
determine the optimal solution at Node 8. Did your incumbent solution change?
(4 points)

The branching variable selected at Node 6 is 𝑥4.

Setting 𝑥4 ≥ 1, we get to Node 8,
and the LP solution at this node yields: 𝑥8= (2, 0, 3, 1) with 𝑧8=− 4 (Solved in excel)

Yes. Incumbent solution changed to node 8 with 𝑧8=− 4

h) Can the branch-and-bound process be terminated at this stage? If yes, explain your
reasoning. If not, continue branching and determine the optimal solution to the
problem. (2 points)

Yes, the branch-and-bound process can be stopped at this stage.

The only other active node at this stage is Node 7. But, Node 6 has a lower bound of
𝑧6=− 4.5, and therefore the best integer solution that we can possibly be obtained by
solving Node 7 cannot be better than the current incumbent. Therefore, Node 7 can
be fathomed by bound.

Also, adding constraint X4<=0 doesn’t satisfy the second constraint 7X1+3X2−
4X3−2X4 ≤1. Thus node 7 can be fathomed by infeasibility.

We can declare that 𝑥8= (2, 0, 3, 1) is the optimal solution with 𝑧8=− 4 as the optimum
objective function value.