0

My Pyomo model is trying to solve a task assignment problem where 4 workers needs to be assigned to 8 tasks, so that's 2 tasks per worker.

One of the objective function model.obj2 tries to minimize the sum of the types of materials used by each worker worker. The reason is because every truck transporting materials to the worker can only carry 1 type of material, so there is efficiency gains to minimize the total number of truck visits.

This is currently being done using len(set(...)) to find number of unique materials used by both tasks assigned to a worker, and sum() to add up this number for all 4 workers.

def obj_rule(m):
    # Minimize the total costs
    obj1 = sum(
        costs[i][j] * model.x[w, t] for i, w in enumerate(W) for j, t in enumerate(T)
    )

    # Minimize the number of unique materials used per worker
    obj2 = len(
        set(
            material
            for w in W
            for t in T
            for material in materials_used[t]
            if value(model.x[w, t]) == True
        )
    )
    return  5 * obj1 + 2 * obj2

However, removing model.obj1 (for debugging purposes), such as

def obj_rule(m):
    # Minimize the number of unique materials used per worker
    obj2 = len(
        set(
            material
            for w in W
            for t in T
            for material in materials_used[t]
            if value(model.x[w, t]) == True
        )
    )
    return obj2

results in the warning

WARNING: Constant objective detected, replacing with a placeholder to prevent solver failure.

This might explain why model.obj2 does not seem to be minimized for in the initial code. The objective expression might have been converted into a scalar value?

Can I get some help to rewrite this objective function the proper way for Pyomo? Thank you!

Code to reproduce problem

from pyomo.environ import *
import numpy as np

# 4 workers X 8 tasks
costs = np.array(
    [
        # workerA
        [1, 2, 3, 4, 5, 6, 7, 8],
        [1, 2, 3, 4, 5, 6, 7, 8],
        # workerB
        [8, 7, 6, 5, 4, 3, 2, 1],
        [8, 7, 6, 5, 4, 3, 2, 1],
        # workerC
        [1, 3, 5, 7, 9, 11, 13, 15],
        [1, 3, 5, 7, 9, 11, 13, 15],
        # workerD
        [15, 13, 11, 9, 7, 5, 3, 1],
        [15, 13, 11, 9, 7, 5, 3, 1],
    ]
)

# "stone", "wood", "marble", "steel", "concrete"
materials_used = {
    "taskA": ["stone", "wood"],
    "taskB": ["marble", "wood"],
    "taskC": ["marble", "stone"],
    "taskD": ["steel", "stone"],
    "taskE": ["marble", "steel"],
    "taskF": ["marble", "steel"],
    "taskG": ["concrete", "marble"],
    "taskH": ["concrete", "steel"],
}

W = [
    "workerA1",
    "workerA2",
    "workerB1",
    "workerB2",
    "workerC1",
    "workerC2",
    "workerD1",
    "workerD2",
]
T = ["taskA", "taskB", "taskC", "taskD", "taskE", "taskF", "taskG", "taskH"]

model = ConcreteModel()
model.x = Var(W, T, within=Binary, initialize=0)


def obj_rule(m):
    # Minimize the total costs
    # obj1 = sum(
    #     costs[i][j] * model.x[w, t] for i, w in enumerate(W) for j, t in enumerate(T)
    # )

    # Minimize the number of unique materials used per worker
    obj2 = len(
        set(
            material
            for w in W
            for t in T
            for material in materials_used[t]
            if value(model.x[w, t]) == True
        )
    )
    return  obj2
    # return  5 * obj1 + 2 * obj2


model.obj = Objective(
    rule=obj_rule,
    sense=minimize,
)


def all_t_assigned_rule(m, w):
    return sum(m.x[w, t] for t in T) == 1


def all_w_assigned_rule(m, t):
    return sum(m.x[w, t] for w in W) == 1


model.c1 = Constraint(W, rule=all_t_assigned_rule)
model.c2 = Constraint(T, rule=all_w_assigned_rule)

opt = SolverFactory("glpk")
results = opt.solve(model)
AirSquid
  • 10,214
  • 2
  • 7
  • 31
Athena Wisdom
  • 6,101
  • 9
  • 36
  • 60
  • For counting use binary variables. Note that Pyomo cannot handle just any Python code as part of non-linear expressions. There are restrictions to what you can use. – Erwin Kalvelagen Apr 08 '22 at 19:29
  • @ErwinKalvelagen Any example on how binary variables can be used for counting the number of unique materials used by each worker? I can't seem to figure this out – Athena Wisdom Apr 09 '22 at 04:47
  • Here is an example of an OBJ function that makes use of the binary variables in a summation. You are close here, it is just the core concept that the functions you use to generate the modeling expressions must yield expressions in terms of the variables and constants only as *the value of the variable is unknown when the expression is built*, so `len()` is invalid. https://stackoverflow.com/questions/65186769/defining-specific-set-of-values-for-2-variables-in-pyomo/65188699#65188699 – AirSquid Apr 09 '22 at 14:40
  • You are on the right track. I’d encourage you to think about (1) reformulating your set of workers to just `[‘A’, ‘B’, ‘C’, ‘D’]` as you could then sum by worker to check for jobs assigned and (2) then collapse your costs down into a dictionary indexed the same way and make it a model parameter….much cleaner – AirSquid Apr 09 '22 at 14:45
  • @AirSquid Thanks for the references, I looked through them and thought more about using binary variables for counting, but I still cannot figure out how to count the unique number of materials used. I can only manage to use binary variables to count the number of materials used including duplicates – Athena Wisdom Apr 10 '22 at 05:43
  • @AirSquid For example, I can figure out how to arrive at a worker requiring `["concrete", "marble", "concrete", "steel"]` which gives a value of `4` in the objective function, but I need to calculate the number of unique materials used by each worker, i.e. `["concrete", "marble", "steel"]` which gives a value of `3` in the objective function – Athena Wisdom Apr 10 '22 at 05:45

1 Answers1

2

I think there are 2 things I can add here that might be your missing links...

First, as mentioned in comments, the stuff you feed into the model must be legal expressions that do not depend on the value of the variables at time of creation, so len() etc. are invalid. Solution: use binary variables for those types of counting things and then sum them over appropriate indices.

Second, you are indexing your first variable correctly, but you have a second variable you need to introduce, namely, the decision to send worker w some material matl. See my example below that introduces this variable and then uses a big-M constraint to link the two decisions together.... Specifically, ensure the model delivers a required material to a worker for a task in which it is required.

Code:

# worker-task-material assignement
# goal:  assign workers to tasks, minimze cost of sending them materials
#        individually with a weighted OBJ function

import pyomo.environ as pyo

# some data

tasks = list('ABCDEF')
matls = ['stone', 'steel', 'wood', 'concrete']

big_M = max(len(tasks), len(matls))  # an upper bound on the num of matls needed

# this could be expanded to show quantities required...
material_reqts = [
    ('A', 'stone'),
    ('A', 'steel'),
    ('A', 'wood'),
    ('B', 'stone'),
    ('B', 'concrete'),
    ('C', 'concrete'),
    ('D', 'steel'),
    ('D', 'concrete'),
    ('E', 'stone'),
    ('E', 'wood'),
    ('F', 'steel'),
    ('F', 'wood')]

# convert to dictionary for ease of ingestion...
matls_dict = {(task, matl) : 1 for (task, matl) in material_reqts}

workers = ['Homer', 'Marge', 'Flanders']

# a little delivery cost matrix of matl - worker
worker_matl_delivery_costs = [
    [1, 2, 4, 5],   # Homer
    [2, 3, 1, 1],   # Marge
    [4, 4, 3, 2]]   # Flanders

wm_dict = { (w, m) : worker_matl_delivery_costs[i][j]
            for i, w in enumerate(workers)
            for j, m in enumerate(matls)}

# salary matrix
worker_task_costs = [
    [2.2, 3.5, 1.9, 4.0, 3.8, 2.1],
    [1.5, 3.0, 2.9, 4.0, 2.5, 1.6],
    [1.4, 4.0, 2.3, 4.4, 2.5, 1.8]]

wt_dict = { (w, t) : worker_task_costs[i][j]
            for i, w in enumerate(workers)
            for j, t in enumerate(tasks)}

# build model components...
m = pyo.ConcreteModel()

# SETS
m.W = pyo.Set(initialize=workers)
m.T = pyo.Set(initialize=tasks)
m.M = pyo.Set(initialize=matls)

# PARAMS
m.delivery_costs = pyo.Param(m.W, m.M, initialize=wm_dict)
m.salary_costs =   pyo.Param(m.W, m.T, initialize=wt_dict)
# note:  need a default here to "fill in" the non-requirements...
m.matl_reqts =     pyo.Param(m.T, m.M, initialize=matls_dict, default=0)

# VARS
m.Assign =  pyo.Var(m.W, m.T, domain=pyo.Binary)  # assign worker to task decision
m.Deliver = pyo.Var(m.W, m.M, domain=pyo.Binary)  # deliver material to worker decision

# build model

# OBJ

# some conveniences here....  we can make model expressions individually
# for clarity and then combine them in the obj.  
# pyo.summation() is a nice convenience too!  Could also be done w/generator
delivery = pyo.summation(m.delivery_costs, m.Deliver)
salary = pyo.summation(m.salary_costs, m.Assign)
w1, w2 = 0.5, 0.6  # some arbitrary weights...
m.OBJ = pyo.Objective(expr=w1 * delivery + w2 * salary)

# CONSTRAINTS

# each worker must do at least 2 tasks.  (note:  this is an extension of your reqt.
# in this in conjunction with constraint below will pair all 6 tasks (2 ea. to workers)
# if more tasks are added, they'll be covered, with a min of 2 each

def two_each(m, w):
    return sum(m.Assign[w, t] for t in m.T) >= 2
m.C1 = pyo.Constraint(m.W, rule=two_each)

# each task must be done once...prevents tasks from being over-assigned
def task_coverage(m, t):
    return sum(m.Assign[w, t] for w in m.W) >= 1
m.C2 = pyo.Constraint(m.T, rule=task_coverage)

# linking constraint....  must deliver materials for task to worker if assigned
# note this is a "for each worker" & "for each material" type of constraint...

def deliver_materials(m, w, matl):
    return m.Deliver[w, matl] * big_M >= sum(m.Assign[w, t] * m.matl_reqts[t, matl]
        for t in m.T)
m.C3 = pyo.Constraint(m.W, m.M, rule=deliver_materials)

solver = pyo.SolverFactory('glpk')
results = solver.solve(m)
print(results)

print('Assignment Plan:')
for (w, t) in m.Assign.index_set():
    if m.Assign[w, t]:
        print(f'  Assign {w} to task {t}')

print('\nDelivery Plan:')
for w in m.W:
    print(f'  Deliver to {w}:')
    print('    ', end='')
    for matl in m.M:
        if m.Deliver[w, matl]:
            print(matl, end=', ')
    print()
print()

Yields:

Problem: 
- Name: unknown
  Lower bound: 18.4
  Upper bound: 18.4
  Number of objectives: 1
  Number of constraints: 22
  Number of variables: 31
  Number of nonzeros: 85
  Sense: minimize
Solver: 
- Status: ok
  Termination condition: optimal
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 53
      Number of created subproblems: 53
  Error rc: 0
  Time: 0.008975028991699219
Solution: 
- number of solutions: 0
  number of solutions displayed: 0

Assignment Plan:
  Assign Homer to task A
  Assign Homer to task F
  Assign Marge to task B
  Assign Marge to task E
  Assign Flanders to task C
  Assign Flanders to task D

Delivery Plan:
  Deliver to Homer:
    stone, steel, wood, 
  Deliver to Marge:
    stone, wood, concrete, 
  Deliver to Flanders:
    steel, concrete, 

[Finished in 562ms]
AirSquid
  • 10,214
  • 2
  • 7
  • 31