Эквивалент Populate() для MIQP в CPLEX

Я пытаюсь решить проблему 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)
 

person jolene    schedule 07.04.2021    source источник
comment
1) cplex говорит, что эта функция недоступна для MIQP, независимо от того, бесплатный/несвободный python или не-python. 2) Я ожидаю, что проблема MWIS будет сформулирована как MILP, а не MIQP. Вы уверены, что ваша модель - это то, что вам нужно? 3) Ваша модель MIQP != из-за продуктов bin-var. Вам это нужно? (классическая формулировка: нет!) Вы можете (не то чтобы это всегда хорошая идея) линеаризовать это вручную или, возможно, использовать параметр cplex, чтобы линеаризовать это автоматически, что должно снова сделать проблему MILP, чтобы ваша функция вернулась.   -  person sascha    schedule 07.04.2021


Ответы (1)


При объединении решений в пул можно вызвать множество решений и удалить предыдущие решения.

Пример в https://github.com/AlexFleischerParis/zoodocplex/blob/master/zooenumeratewithoutsolutionpool.py

from docplex.mp.model import Model


mdl = Model(name='buses')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')
mdl.add_constraint(nbbus40*40 + nbbus30*30 >= 300, 'kids')
mdl.minimize(nbbus40**2*500 + nbbus30**2*400)

nb_iter=5

for iter in range(0,nb_iter):
    mdl.solve()
    nbbus40sol=int(nbbus40.solution_value)
    nbbus30sol=int(nbbus30.solution_value)
    print(int(nbbus40sol)," buses 40 seats")
    print(int(nbbus30sol)," buses 30 seats")
    print("cost : ",mdl.objective_value)
    print()
    mdl.add_constraint(mdl.logical_or((nbbus40sol!=nbbus40),
            nbbus30sol!=nbbus30))

который дает

4  buses 40 seats
5  buses 30 seats
cost :  18000.0
5  buses 40 seats
4  buses 30 seats
cost :  18900.0
3  buses 40 seats
6  buses 30 seats
cost :  18900.0
6  buses 40 seats
2  buses 30 seats
cost :  19600.0
6  buses 40 seats
3  buses 30 seats
cost :  21600.0
person Alex Fleischer    schedule 08.04.2021
comment
Спасибо за этот ответ, я нашел другой способ (я все равно вычисляю все возможные значения, поэтому могу просто выполнить поиск)! - person jolene; 10.04.2021