This file computes the solution to an assignment problem - Problem 4 on the Midterm Exam - using Pyomo.

This problem is interesting because it has multiple solutions. A solver based on the simplex method, e.g. GLPK, will return a corner point feasible solution which satisfies the integrality property. An interior point solver, e.g. Ipopt, will generally not converge to a corner point feasible solution, thus the returned optimal solution will generally not be integer.

from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk") 
# Change to "ipopt" for interior point solver

An assignment problem is a special case of a transportation problem where the "supply" and "demand" constants are identically one, so we simply follow the established coding pattern.

M = ['A', 'B', 'C']
W = ['D', 'E', 'F']

c = {('A','D'):1, ('A','E'):3, ('A','F'):3,
     ('B','D'):4, ('B','E'):3, ('B','F'):2,
     ('C','D'):5, ('C','E'):4, ('C','F'):2}

model = ConcreteModel()

model.x = Var(M, W, within=NonNegativeReals)

model.z = Objective(expr = sum(c[i,j]*model.x[i,j]
                               for i in M for j in W), 
                    sense=maximize)

def all_m_assigned_rule (model, i):
    return sum(model.x[i,j] for j in W) == 1

model.m = Constraint(M, rule=all_m_assigned_rule)

def all_w_assigned_rule (model, j):
    return sum(model.x[i,j] for i in M) == 1

model.w = Constraint(W, rule=all_w_assigned_rule)

results = opt.solve(model)

Here the model output for the GLPK solver run:

model.x.get_values()

{('A', 'D'): 0.0,
 ('A', 'E'): 0.0,
 ('A', 'F'): 1.0,
 ('B', 'D'): 1.0,
 ('B', 'E'): 0.0,
 ('B', 'F'): -0.0,
 ('C', 'D'): -0.0,
 ('C', 'E'): 1.0,
 ('C', 'F'): 0.0}

model.z.expr()

11.0

For comparison, a copy-paste of the Ipopt solver output. Note how the interior point method solution is qualitatively different.

# In [3]: model.x.get_values()
# 
# Out[3]: {('A', 'D'): 0.0,
#          ('A', 'E'): 0.0,
#          ('A', 'F'): 1.0000000137507596,
#          ('B', 'D'): 0.5291569866857398,
#          ('B', 'E'): 0.4708430186888719,
#          ('B', 'F'): 0.0,
#          ('C', 'D'): 0.4708430225887518,
#          ('C', 'E'): 0.5291569857873947,
#          ('C', 'F'): 0.0}
#
# In [4]: model.z.expr()
# 
# Out[4]: 11.000000100155193