Skip to content

Instantly share code, notes, and snippets.

@sschnug
Last active June 5, 2018 16:29
Show Gist options
  • Save sschnug/eab13d7d79736d5b885724aaf1c67806 to your computer and use it in GitHub Desktop.
Save sschnug/eab13d7d79736d5b885724aaf1c67806 to your computer and use it in GitHub Desktop.
""" IMPORTANT REMARK:
This is an IP-approach.
Simple examples, like the one given in the question, result in a model for which it SEEMS, produce integral basic feasible solutions.
This MIGHT indicate that the constraint matrix is totally unimodular and no IP/branching is necessary as an pure LP-solver will do.
To try this, change the following:
x = cvx.Variable((N_BLOCKS, N_SLOTS)) #, boolean=True) = now continuous variables
constraints = [x >= 0, x <= 1] # bound continuous vars to [0,1]
I'm too lazy to check the underlying math for now / (or modify cvxpy to get me my final constraint-matrix too look at).
"""
""" INTEGER PROGRAMMING """
import cvxpy as cvx
# PROBLEM
# -------
ALLOWED = [[0, 1, 2],
[0, 2],
[0, 1, 2],
[0, 1],
[1, 2],
[0, 1, 2],
[0, 1, 2],
[0, 1, 2],
[1, 2]]
N_BLOCKS = len(ALLOWED)
N_SLOTS = max([len(x) for x in ALLOWED])
# Vars
# ----
x = cvx.Variable((N_BLOCKS, N_SLOTS), boolean=True)
# Constraints
# -----------
constraints = []
# each block assigned exactly once
for block in range(N_BLOCKS):
constraints.append(sum(x[block, :]) == 1)
# some block-slot assignments are not allowed
# inefficient in terms of:
# coding
# mathematical-optimization
for block in range(N_BLOCKS):
not_allowed = list(set(range(N_SLOTS)) - set(ALLOWED[block]))
for slot in not_allowed:
constraints.append(x[block, slot] == 0)
# Objective
# ---------
obj = cvx.Maximize(cvx.min(cvx.sum(x, axis=0)))
# Solve
# -----
prob = cvx.Problem(obj, constraints)
# Solver CBC not shipped by default
# Solver ECOS_BB can only solve toy-instances and returns non-basic solutions
# -> want to round these
prob.solve(solver='CBC', verbose=False)
print("status:", prob.status)
print("optimal value", prob.value)
print("optimal distribution")
print(x.value)
# status: optimal
# optimal value 3.0
# optimal distribution
# [[1. 0. 0.]
# [0. 0. 1.]
# [0. 1. 0.]
# [0. 1. 0.]
# [0. 0. 1.]
# [1. 0. 0.]
# [1. 0. 0.]
# [0. 1. 0.]
# [0. 0. 1.]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment