Constraint programming

%22Illustration%20on%20a%20black%20background%20depicting%20the%20concept%20of%20'constraint%20programming'.%20A%20set%20of%20interconnected%20nodes%2C%20each%20labeled%20as%20a%20variable%2C%20with%20chains%20or%20links%20representing%20constraints.%20Some%20nodes%20glow%20to%20indicate%20they%20are%20satisfying%20their%20constraints%2C%20while%20others%20are%20dim%20to%20show%20they%20aren't.%22

"Illustration on a black background depicting the concept of 'constraint programming'. A set of interconnected nodes, each labeled as a variable, with chains or links representing constraints. Some nodes glow to indicate they are satisfying their constraints, while others are dim to show they aren't."

Constraint programming is a programming paradigm where relationships between variables are expressed as constraints. The objective is to find values for these variables that satisfy all given constraints. It is particularly useful for solving combinatorial problems, such as scheduling, planning, and resource allocation, where traditional algorithms might be inefficient. Instead of specifying steps to achieve a solution, one defines the desired properties of a solution, and the system determines a valid assignment, if one exists.

Constraint Satisfaction Problem

A Constraint Satisfaction Problem (CSP) is a mathematical problem defined by a set of variables, a domain of possible values for each variable, and a collection of constraints specifying permissible combinations of values. The goal is to assign values to the variables such that all constraints are satisfied. Common examples include the Sudoku puzzle, where each cell is a variable, digits 1-9 are the domain, and the rules of Sudoku are the constraints. Other examples:

eight queen problems

map coloring problem

Exercise: Adam and Eve scheduling

Adam and Eve are happily married and have two cute sons, Cain and Abel. In general they love each other, but sometimes divirgent opinions relating to house management lead to unnecessary conflicts. To reduce such conflicts, Adam proposes to optimize, starting with following facts: there are four rooms (kitchen, bath, living room, sleeping room) in their house and they want to have each room in an absolutely clean state at least once in a week. Cleaning of sleeping room and bathroom necessitate investment of 2 hours each, cleaning of living room and kitchen costs 3 hours each. In order to keep family healthy & restauration costs low, a hot meal is cooked at least 4 times in a week and children also demand one cake a week. Cooking takes 1 hour, baking 2 hours. After cooking or baking, kitchen becomes dirty and Eve demands that kitchen is clean on Sunday evening. Adam has one hour time on Monday and Wednesday, three hours time on Thursday and fours hours time on each weekend day, Eve has two hours on Tuesday, three hours on Friday and four hours on each weekend day. Ideally, they would like to maximize the amount of time they invest into cleaning & cooking.

Optional: Act of bringing little Cain & Abel to a playground for two hours results in less entropy at home and thus reduces living room cleaning cost to two.

Assignment

Everyone: define tasks (and their lengths), resources (and their availability), precedence relations (if any), capacity constraints (if any) and costs of optional tasks (if any)

IOPS group: find the optimal solution using some constraint programming library (GPT4 can show You how to use it)

Solution

      
      
        #Adam has one hour time on Monday and Wednesday, three hours time on Thursday and fours hours time on each weekend day, Eve has two hours on Tuesday, three hours on Friday and four hours on each weekend day.  Define pyschedule resources with correctly defined periods and horizons.

#Monday: Adam x 1
#Tuesday:  Eva x 2
#Wednesday: Adam x 1
#Thursday: Adam x 4
#Friday: Eva x 3
#Saturday: Both x 4
#Sunday : Both x 4

from pyschedule import Scenario, solvers, plotters, alt

# Define the scenario
S = Scenario('household_chores', horizon=15)  # Two weeks

# Define the resources, resource costs are not obligatory but it's more fun with them
adam = S.Resource('Adam',periods=[0,3,4,5,6,7,11,12,13,14])
eve = S.Resource('Eve',periods=[1,2,8,9,10,11,12,13,14])

kitchen=S.Resource('kitchen')

# Define the tasks and their durations
task_costs = {
    "meal1": {"length":1,"delay_cost":1},                # 1 hour, schedule towards beginning of the week
    "meal2": {"length":1,"delay_cost":1},             
    "meal3": {"length":1,"delay_cost":-1},               
    "meal4": {"length":1,"delay_cost":-1},               # 1 hour, schedule towards end of the week
    "bake": {"length":2,"delay_cost":0},                  # 2 hours (1 cake)
    "sleeping_room": {"length":2,"delay_cost":0},  # it seems there is a bug for tasks longer >1 
    #"CSR1": {"length":1,"delay_cost":0},          # one way how to address the bug is to split long tasks into sub-tasks coupled by tight preference constraints
    #"CSR2": {"length":1,"delay_cost":0},          # 
    "bathroom": {"length":2,"delay_cost":0},       # 2 hours
    "living_room": {"length":3,"delay_cost":0},    # 3 hours
    "clean_kitchen": {"length":3,"delay_cost":0}   # 3 hours
}

tasks={}
# Define alternative resources for each task
for task,costs in task_costs.items():
    print(task,costs)
    tasks[task] = S.Task(task,length=costs['length'],delay_cost=costs["delay_cost"])      #create new task
    tasks[task] += adam | eve               #assign resources to newly created task

#additional task-resource attributions
tasks["clean_kitchen"]+=kitchen
tasks["meal1"]+=kitchen
tasks["meal2"]+=kitchen
tasks["meal3"]+=kitchen
tasks["meal4"]+=kitchen
tasks["bake"]+=kitchen

#tight precedence constraints
#S += tasks['CSR1'] <= tasks['CSR2']

#optional tasks
#tasks['playground'] = S.Task('playground',length=2,schedule_cost=-1)
#tasks['playground'] += alt(adam,eve)

#additional constraints
S += tasks['meal1'] < tasks['clean_kitchen'] 
S += tasks['meal2'] < tasks['clean_kitchen'] 
S += tasks['meal3'] < tasks['clean_kitchen'] 
S += tasks['meal4'] < tasks['clean_kitchen'] 
S += tasks['bake'] < tasks['clean_kitchen'] 

# Solve the scenario
solvers.mip.solve(S,msg=1,kind='GUROBI')

print(S)
print(S.solution())
print(adam.periods)
# Plot the schedule
plotters.matplotlib.plot(S)

      
    

Python libraries

pyschedule example

https://github.com/python-constraint/python-constraint

https://github.com/timnon/pyschedule

Note: install the most recent fork, (e.g. pip3.10 install "pyschedule"@git+"https://github.com/ppoile/pyschedule/#subdirectory=src")