NP: Easy to verify a solution
SAT
all([
v1 or not v2 or v3,
not v1 or not v3,
v1 or v2,
])
v1 = False
v2 = True
v3 = True
ILP
all([
0 <= v1 <= 1,
0 <= v2 <= 1,
0 <= v3 <= 1,
v1 + (1 - v2) + v3 >= 1,
(1 - v1) + (1 - v3) >= 1,
v1 + v2 >= 1
])
v1 = 0
v2 = 1
v3 = 1
import pulp
v1 = pulp.LpVariable('v1', cat='Binary')
v2 = pulp.LpVariable('v2', cat='Binary')
v3 = pulp.LpVariable('v3', cat='Binary')
problem = pulp.LpProblem()
problem.addConstraint(v1 + (1 - v2) + v3 >= 1)
problem.addConstraint((1 - v1) + (1 - v3) >= 1)
problem.addConstraint(v1 + v2 >= 1)
problem.solve(pulp.solvers.GLPK(msg=0))
print("v1 =", pulp.value(v1))
print("v2 =", pulp.value(v2))
print("v3 =", pulp.value(v3))
v1 = 1.0
v2 = 0.0
v3 = 0.0
import pulp
def pack_knapsack(items, capacity):
problem = pulp.LpProblem()
inclusions = [
pulp.LpVariable('I%d' % (i,), cat='Binary')
for i in range(len(items))
]
problem.addConstraint(sum(
weight * included
for (weight, _), included in zip(items, inclusions)) <= capacity)
problem.sense = pulp.constants.LpMaximize
problem.objective = sum(
value * included for (_, value), included in zip(items, inclusions))
problem.solve(pulp.solvers.GLPK(msg=0))
return [
item for item, included in zip(items, inclusions)
if pulp.value(included) > 0
]
def arrange_talks(talks, rooms, slots):
problem = pulp.LpProblem()
variables = {
(t, r, s): pulp.LpVariable(
"Schedule_%d_%d_%d" % (t, r, s), cat='Binary')
for t in talks for r in rooms for s in slots
}
... # TODO: constraints go here
... # TODO: what to optimize by??
problem.solve(pulp.solvers.GLPK(msg=0))
return [
assignment for assignment, variable in variables.items()
if pulp.value(variable) > 0
]
for t in talks:
problem.addConstraint(sum(
variables[(t, r, s)]
for r in rooms for s in slots
) == 1)
for r in rooms:
for s in slots:
problem.addConstraint(sum(
variables[(t, r, s)] for t in talks
) <= 1)
for t in talks:
for s in slots:
if not speaker_is_available(t, s):
for r in rooms:
problem.addConstraint(
variables[(t, r, s)] == 0
)
for speaker in speakers:
for s in slots:
for t in speaker.talks:
problem.addConstraint(sum(
variables[(t, r, s)] for r in rooms
) <= 1)
disappointments = []
for t in talks:
capacity = sum(
room_capacity(r) * variables[(t, r, s)]
for r in rooms for s in slots
)
d = pulp.LpVariable(
'Disappointment_%d' % (t,)
cat='Integer', lowBound=0
)
disappointments.append(d)
problem.addConstraint(d >= interest_in(talk) - capacity)
problem.sense = pulp.constants.LpMinimize
problem.objective = sum(disappointments)
problem.sense = pulp.constants.LpMaximize
problem.objective = sum(
variables[(t, r, s)]
for (t, r, s) in previous_schedule_version
)