This file shows how to code up the solution to the "Museum Problem" on the Fall 2020 Midterm, Question 4, in Pyomo.

In [1]:
from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk")

We code up the doors of the museum as arcs of a network. The rooms are the vertices; they can be extracted automatically from the list of arcs.

In [2]:
A = [('A','B'), ('B','H'), ('H','I'), ('I','G'),
     ('G','A'), ('I','J'), ('A','F'), ('F','D'),
     ('A','C'), ('C','D'), ('D','E')]

R = {a[0] for a in A} | {a[1] for a in A}

The rest is a straightforward implementation of the model as specified in the sample solutions.

In [3]:
model = ConcreteModel()

model.x = Var(A, within=Boolean)

model.z = Objective(
    expr = sum(model.x[a] for a in A), sense=minimize)

def all_rooms_are_guarded_rule (model, i):
    return sum(model.x[a] for a in A if i in a) >= 1

model.c = Constraint(R, rule=all_rooms_are_guarded_rule)

results = opt.solve(model)
In [4]:
model.x.get_values()
Out[4]:
{('A', 'B'): 0.0,
 ('B', 'H'): 1.0,
 ('H', 'I'): 0.0,
 ('I', 'G'): 1.0,
 ('G', 'A'): 0.0,
 ('I', 'J'): 1.0,
 ('A', 'F'): 1.0,
 ('F', 'D'): 0.0,
 ('A', 'C'): 1.0,
 ('C', 'D'): 0.0,
 ('D', 'E'): 1.0}
In [5]:
model.z.expr()
Out[5]:
6.0