https://stackoverflow.com/questions/50699944/algorithm-to-get-maximum-yield

so_prod_opt.py

""" 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.]]