CPLEX - Minimum eines Matrix-Subsets

Question

Ich benutze die Python-API zu cplex, um ein Optimierungsproblem zu lösen: Finden der Menge der binären Variablen der Größe N (z. B. 10), um ihren gegenseitigen Abstand zu maximieren. Um dies zu tun, ich habe zusammen folgendes gesagt:

matrix = pd.read_csv("matrix.csv", index_col=0) 

# declare integer variables 
im = Model(name='max_weight_clique') 
b = im.binary_var_dict(matrix.index.values) 

# define objective function 
clique_weight = im.sum(b[i] * b[j] * (matrix.loc[i, j] + matrix.loc[j, i]) 
          for i, j in itertools.combinations(matrix.index, 2)) 
# add to key performance indicators 
im.add_kpi(clique_weight, 'clique_weight') 

# set size of clique 
im.add_constraint(im.sum(b) == 10) 

im.maximize(clique_weight) 

Ich mag würde meine Zielfunktion, sondern maximieren den Mindestabstand ändern. Wenn ich versuche, dies als die folgenden angeben, betreibe ich in einen Fehler:

# minimum within clique 
clique_min = im.min(adj_mat.loc[i, j] for i in adj_mat.index for j in adj_mat.index if b[i] == 1 and b[j] == 1) 
im.add_kpi(clique_min, 'clique_min') 

TypeError: cannot convert a constraint to boolean: acc_num_NC_015394 == 1

Wie soll ich diese Einschränkung korrekt angeben? Dies scheint mit diesem SO verwandt zu sein, aber mein Problem ist spezifisch für die Python-API.

Answer 1

Das Problem in Ihrer Formulierung ist, dass die '==' Tests mit binären Entscheidungsvariablen in den Iteratoren nicht als Modelleinschränkungen erkannt werden.

Eine Option zum Modellieren dieser Art von Einschränkung ist die Verwendung von Indikatorbeschränkungen. Hier ist eine mögliche Formulierung für Ihr Beispiel:

bij_ind = im.binary_var_matrix(matrix.index.values, matrix.index.values, name='ind_') 
clique_min = im.continuous_var(name='clique_min') 
for i in matrix.index: 
    for j in matrix.index: 
     im.add(bij_ind[i, j] == im.min(b[i], b[j])) 
     im.add_indicator(bij_ind[i, j], clique_min <= adj_mat.loc[i, j]) 

im.add_kpi(clique_min, 'clique_min') 
im.maximize(clique_min) 

Ich glaube nicht, diese Formulierung jedoch sehr effizient ist.