Я пытаюсь решить проблему MWIS именно с помощью CPLEX. Когда я пробую .populate()
, я получаю сообщение об ошибке docplex.mp.utils.DOcplexException: Model.populate_solution_pool only for MILP problems, model 'Exact Solution' is a MIQP
.
Есть ли способ использовать бесплатную загрузку CPLEX для Python, чтобы получить более одного возможного решения?
def get_exact_solution(Graph,model_name ='Exact Solution (s)'):
model = new_docplex_generator(Graph,model_name)
solution = model.solve() # this works
solutions = model.populate() # this doesn't
print("Multi?")
print(solutions)
Это код, который я использую в сочетании с решателем!
def weighted_erdos_graph(nodes, prob, seed =None):
"""Generates an erdos graph with weighted nodes
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
Node weights randomly assigned with the same seed as the erdos graph
"""
graph = nx.erdos_renyi_graph(n=nodes, p =prob, seed=seed, directed=False)
np.random.seed(seed)
graph_weights = np.random.randint(1,high=11,size =nodes)
name = str("Erdos Graph "+str(nodes)+" nodes weighted "+str(list(graph_weights)))
graph.nodes[0]["graph_name"] = name
for i in range(0,nodes):
graph.nodes[i]["node_weight"] = graph_weights[i]
#print(list(graph.nodes(data=True)))
return graph
def new_docplex_generator(G,model_name):
'''
Takes in a networkx graph with weighted nodes and creates the docplex model for the
MWIS
'''
mdl = Model(model_name)
n = G.number_of_nodes()
x = mdl.binary_var_list('x_{}'.format(i) for i in range(n)) #creates list of variables for each node
node_list = list(G.nodes())
node_weights = G.nodes(data='node_weight')
just_weights = [weight[1] for weight in node_weights] #gets just the node weight
scale = max(just_weights) # used as J_i,j must be greater than weight of node; all node weights are scaled to below 0 and J_ij is put as 2
edge_list = list(G.edges())
#node_weight_terms = mdl.sum([x[i] * -1*(just_weights[i]/scale) for i in node_list])
node_weight_terms = mdl.sum([x[i] * -1*(just_weights[i]) for i in node_list])
edge_indepedence_terms = mdl.sum([20*x[i]*x[j] for (i,j) in edge_list])
mdl.minimize(node_weight_terms + edge_indepedence_terms) # does this need to be minimise ?
print("auto_docplex_function")
mdl.prettyprint()
return mdl
get_exact_solution(unweighted_erdos_graph(7,0.5,seed = 3)