组合最小化

Question

我正在尝试找到最有效的方法。

学生可以被分配到停靠站 A、B 或 C。我们会得到一份学生有资格被分配到的停靠站列表。

##Create an empty dataframe
df = pd.DataFrame()

## Create a list with potential stops that each student qualifies for

potential_stops_for_each_student = [['A','B','C'], ['B','C'], ['C']]
df['Potential Stops'] = potential_stops_for_each_student

我的目标是尽量减少停靠站的总数，因此在此示例中，显然所有学生都应分配到公交车站 'C'。我的解决方案目前着眼于所有可能的组合（即（A，B，C），（A，C，C），（B，B，C），（B，C，C），（C，B，C）， (C,C,C)), 然后选择唯一元素最少的组合。

这对我来说似乎是一个糟糕的解决方案，所以我希望有人能指出我更好的解决方案。对包或任何现有文献的引用都可以，如果你不想，你不必编写代码！

谢谢！

Answer 1

下面是使用 cvxpy with the GLPK solver: you will need to install it as well as cvxpy using the instructions here.

的快速尝试

#import the packages:
import numpy as np
import cvxpy

#we will set the number of stops and children here:
nstops = 10
nchildren = 50

#data looks like a 1/0 array for each child, for each stop
#you can use pd.get_dummies to do this
data = np.random.randint(2, size=(nchildren, nstops))

#here we set our cvxpy variable: this varies to find the best solution
#it will be the boolean to determine which stops we chose
selection = cvxpy.Variable(nstops, boolean=True)

#now we make our constraints
#for each child, the sum of the product of the chosen stops and their available stops must be >=1
#we can probably use a better formulation of this, but it works
constraints = []
for i in range(nchildren):
    #we use cvxpy operations to allow the problem to be formulated
    constraints.append(cvxpy.sum(cvxpy.multiply(data[i,:],selection )) >= 1)
   
#now our problem is: minimize the sum of the number of chosen stops:
cost = cvxpy.sum(selection)

#we want to minimize it, subject to our constraints
problem = cvxpy.Problem(cvxpy.Minimize(cost), constraints=constraints)

#then we solve it!
score = problem.solve(solver=cvxpy.GLPK_MI)

#we have our 'selection' as a numpy array of booleans: here we get the indices of the chosen stops
np.where(selection.value.astype(np.bool))

组合最小化

Combinatorial minimisation

python

mathematical-optimization

combinatorics