Python PuLPの目的関数で外部データを使う方法は？

Question

正方形の行列の正方形の固定サイズの部分集合を選択して、部分集合行列の和が最小になるようにしたいとします。いくつかのコード：numpyのインデックスはindsがLpVariablesのリストされて好きではないので、

import nump as np 
import pulp 

def subset_matrix(data, inds): 
    return data[np.ix_(inds, inds)] 

A = np.random.random((10, 10)) 

indices = list(range(len(A))) 

prob = pulp.LpProblem("Minimum subset", pulp.LpMaximize) 

x = pulp.LpVariable.dicts('elem', indices, lowBound=0, upBound=1, cat=pulp.LpInteger) 

prob += pulp.lpSum(subset_matrix(A, [x[i] for i in indices])) 

prob.solve() 

これが失敗しました。これを回避する方法はありますか？パルプ制約にnumpyの配列検索を含めるにはどうすればいいですか？

Answer 1

これはPuLPに関する質問ではなく、混合整数リニアプログラムとして数学問題を適切に定式化する方法の問題です。

最適化するインデックスのセット全体にわたって係数の合計（「サブセットマトリックスの合計」）として目標を表現しようとしているようです。 （ところで、私はサブマトリックス上のサイズ制約がどこに書かれているかわかりません）。しかし、MILPでは、目的は、所定のインデックスセットを上回るコスト係数のベクトルを持つ決定変数のベクトルの内積。したがって、自然な定式化では、決定ベクトルは、バイナリ値を使用してサブマトリクス内にあるように選択した完全インデックスセットからのインデックスを表します。

私があなたがしようとしていることを理解していれば、これはきちんとした問題のようです。私はあなたがIのサブセット{0、1、...、N-1}の固定サイズのサブセットを選択しようとしていると信じています。最大化される。たとえば、大きな行列が10x10で、6x6のサブ行列が必要な場合を考えてみましょう。だから私は{0、...、9}の6つの要素です。

次に、{0、...、9}の両方のi、jの変数x（i、j）を定義します。これは、サブマトリックス用に選択された大きな行列の各要素）、および変数y（i）、i in {0、...、9}を選択する。そして、それらの制約を線形として表現しようとし、y変数をバイナリにして各インデックスが入っているか出ているかを表現します。ここで

は、私はあなたが意味する何を考えての製剤である：

import pulp as pp 
import numpy as np 
import itertools 

##################### 
# Problem Data: # 
##################### 

full_matrix_size = 10 
submatrix_size = 6 

A = np.random.random((full_matrix_size, full_matrix_size)).round(2) 

inds = range(full_matrix_size) 
product_inds = list(itertools.product(inds,inds)) 

##################### 
# Variables:  # 
##################### 

# x[(i,j)] = 1 if the (i,j)th element of the data matrix is in the submatrix, 0 otherwise. 
x = pp.LpVariable.dicts('x', product_inds, cat='Continuous', lowBound=0, upBound=1) 

# y[i] = 1 if i is in the selected index set, 0 otherwise. 
y = pp.LpVariable.dicts('y', inds, cat='Binary') 

prob = pp.LpProblem("submatrix_problem", pp.LpMaximize) 

##################### 
# Constraints:  # 
##################### 

# The following constraints express the required submatrix shape: 
for (i,j) in product_inds: 
    # x[(i,j)] must be 1 if y[i] and y[j] are both in the selected index set. 
    prob += pp.LpConstraint(e=x[(i,j)] - y[i] - y[j], sense=1, rhs=-1, 
          name="true_if_both_%s_%s" % (i,j)) 

    # x[(i,j)] must be 0 if y[i] is not in the selected index set. 
    prob += pp.LpConstraint(e=x[(i,j)] - y[i], sense=-1, rhs=0, 
          name="false_if_not_row_%s_%s" % (i,j)) 

    # x[(i,j)] must be 0 if y[j] is not in the selected index set. 
    prob += pp.LpConstraint(e=x[(i,j)] - y[j], sense=-1, rhs=0, 
          name="false_if_not_col_%s_%s" % (i,j)) 

# The number of selected indices must be what we require:  
prob += pp.LpConstraint(e=pp.LpAffineExpression([(y[i],1) for i in inds]), sense=0, 
         rhs=submatrix_size, name="submatrix_size") 

##################### 
# Objective:  # 
##################### 

prob += pp.LpAffineExpression([(x[pair], A[pair]) for pair in product_inds]) 

print(prob) 

######################## 
# Create the problem: # 
######################## 

prob.writeLP("max_sum_submatrix.lp") 
prob.solve() 

########################## 
# Display the solution: # 
########################## 
print("The following indices were selected:") 
print([v.name for v in prob.variables() if v.name[0]=='y' and v.varValue==1]) 
print("Objective value is " + str(pp.value(prob.objective))) 

私は手取り試験の問題だった推測している....少なくとも学期が終わりました。