baumhaus dot digital :: baumhaus.digital/Design & Computation/Perspectives in Engineering/IOPS/Constraints/Constraint programming

<

p

class

=

„

fragment

“

>

https

://

github

.

com

/

python

-

constraint

/

python

-

constraint

p

><

p

class

=

„

fragment

“

>

https

://

github

.

com

/

timnon

/

pyschedule

p

><

p

class

=

„

fragment

“

>

Note

:

install

the

most

recent

fork

''

(

e

.

g

.

pip3

.

10

install

„

pyschedule

“

@

git

+

„

https

://

github

.

com

/

ppoile

/

pyschedule

/#

subdirectory

=

src

“

)<

br

>

p

>

<

div

>

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

.

<

br

>

div

><

div

><

br

>

div

><

div

>

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

.<

br

>

div

>

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

)<

br

><

br

>

IOPS

group

:

find

the

optimal

solution

using

some

constraint

programming

library

(

GPT4

can

show

You

how

to

use

it

)

#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)

<

pre

>#

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

4from

pyschedule

import

Scenario

''

solvers

''

plotters

''

alt

#

Define

the

scenarioS

=

Scenario

('

household

chores

'''

horizon

=

15

)

#

Two

weeks

#

Define

the

resources

''

resource

costs

are

not

obligatory

but

it

'

s

more

fun

with

themadam

=

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

durationstask

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

taskfor

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

attributionstasks

[

„

clean

kitchen

“

]+=

kitchentasks

[

„

meal1

“

]+=

kitchentasks

[

„

meal2

“

]+=

kitchentasks

[

„

meal3

“

]+=

kitchentasks

[

„

meal4

“

]+=

kitchentasks

[

„

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

constraintsS

+=

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

scenariosolvers

.

mip

.

solve

(

S

''

msg

=

1

''

kind

='

GUROBI

')

print

(

S

)

print

(

S

.

solution

())

print

(

adam

.

periods

)#

Plot

the

scheduleplotters

.

matplotlib

.

plot

(

S

)

pre

>

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

:<

p

class

=

„

fragment

“

>

eight

queen

problems

p

><

p

class

=

„

fragment

“

>

map

coloring

problem

p

>