0

我正在尝试为以下问题找到一个整数规划公式：

根据 2 个标准对项目列表进行排序，由以下成本表示：

  • '位置成本'：取决于项目在列表中的位置
  • “邻居成本”：取决于列表中相邻的两个项目（即项目是直接邻居）

以下适用：

  • 每个物品只能放置一次
  • 列表有一个开始位置 P_1（-> 该位置的项目没有前面的列表项目）
  • 列表有一个结束位置 P_X（-> 该位置的项目没有后续项目）

我使用 PuLP 进行如下所述的公式化，并尝试使用 GLPK_CMD 和 COIN_CMD 进行求解。它适用于 3 个项目，但对于 4 个或更多项目返回“未定义”。据我所知，诸如 DataFrame 'feasible_solution_example' 中描述的订单不会违反约束。谁能冒险猜测为什么求解器找不到解决方案？
非常感谢任何输入和评论。

import pulp 
import numpy as np
import pandas as pd 


############# Size of problem: number of items in the list to be sorted
length_of_list=12
list_of_items=['I'+str(x).zfill(3)  for x in np.arange(1, length_of_list+1)]
list_of_neighbours=['N_I'+str(x).zfill(3)  for x in np.arange(1,length_of_list+1)]
list_of_positions=['P'+str(x).zfill(3) for x in np.arange(1,length_of_list+1)]


############# Cost matrices
random_position_cost=np.random.randint(-length_of_list, length_of_list, [length_of_list,length_of_list])
positional_cost=pd.DataFrame(random_position_cost, index=list_of_items, columns=list_of_positions).astype(int)
random_neighbour_cost=np.random.randint(-length_of_list, length_of_list, [length_of_list,length_of_list])
neigbour_cost=pd.DataFrame(data=random_neighbour_cost, index=list_of_items, columns=list_of_neighbours)

############# This is/should be an example of a feasible solution 
feasible_solution_example=pd.DataFrame(index=list_of_items, columns=(list_of_items + list_of_neighbours))
feasible_solution_example.loc[:, list_of_items]=np.identity(length_of_list)
feasible_solution_example.loc[:, list_of_neighbours[0]]=0
feasible_solution_example.loc[:, list_of_neighbours[1:]]=np.identity(length_of_list)[:,:-1]
feasible_solution_example=feasible_solution_example.astype(int)

############# Model definition 
model = pulp.LpProblem("Optimal order problem ", pulp.LpMinimize)

# Decision variables: 
item_in_position = pulp.LpVariable.dicts("item_in_position ",
                                     ((a, b) for a in feasible_solution_example.index for b in list_of_positions),
                                     cat='Binary')

item_neighbours = pulp.LpVariable.dicts("item_neighbours",
                                     ((a, b) for a in feasible_solution_example.index for b in list_of_neighbours if str('N_' + a)!=b),
                                     cat='Binary')

# Objective Function
model += (
    pulp.lpSum([
        (positional_cost.loc[i, j] * item_in_position[(i, j)])
        for i in feasible_solution_example.index for j in list_of_positions] + 
        [(neigbour_cost.loc[i, j] * item_neighbours[(i, j)])
        for i in feasible_solution_example.index for j in list_of_neighbours if str('N_' + i)!=j]
        )
)    


## Constraints: 
# 1- Every item can take only one position...    
for cur_item in feasible_solution_example.index: 
    model += pulp.lpSum([item_in_position[cur_item, j] for j in list_of_positions]) == 1

# 2-...and every position can only be taken once
for cur_pos in list_of_positions: 
    model += pulp.lpSum([item_in_position[i, cur_pos] for i in feasible_solution_example.index]) == 1

# 3-...item in position 1 can not be the neighbour (ie the preceeding item) to any other item : 
#     -> all neighbour values for any item x + the value for position 1 for this item must add up to 1 
for cur_neighbour in list_of_neighbours: 
    model += pulp.lpSum([item_neighbours[cur_item, cur_neighbour] for cur_item in list_of_items if cur_neighbour!=str('N_' + cur_item)] + 
                         item_in_position[cur_neighbour.split('_')[1], list_of_positions[0]] ) == 1
# 4-...item in the last position can not have any neighbours (ie any preceeding items): 
#     -> all neighbour values of all items + value for the last position must sum up to 1: 
for cur_item in feasible_solution_example.index: 
    model += pulp.lpSum(([item_neighbours[cur_item, cur_neighbour] for cur_neighbour in list_of_neighbours if cur_neighbour!=str('N_' + cur_item)] + 
                         [item_in_position[cur_item,list_of_positions[-1]]])) ==1


# 5-... When two items are neighbours the cost for that combination needs to be "switched on"  
#     -> (e.g. I001 in position P001 and I002 in P002 then I001 and N_I002 must be eqaul to 1) 
for item_x in np.arange(0,length_of_list-1): 
    for neighbour_y in np.arange(0,length_of_list-1): 
        if item_x!=neighbour_y: 
            # Item x would be neighbour with lot y IF:
            for cur_position in np.arange(0,length_of_list-1):
                #...they would have subsequent positions...    
                model += item_neighbours[list_of_items[item_x], list_of_neighbours[neighbour_y]] +1 >= item_in_position[list_of_items[item_x],list_of_positions[cur_position]]  + item_in_position[list_of_items[neighbour_y],list_of_positions[cur_position+1]]


############# Solve 
model.solve()
model.solve(pulp.GLPK_CMD())
model.solve(pulp.COIN_CMD())
print(pulp.LpStatus[model.status])

更新： 感谢您的评论。删除约束后，现在可以使用。

4

0 回答 0