Python cvxopt glpk ilp return первое возможное решение

Question

Я использую cvxopt.glpk.ilp для решения очень сложной смешанной цельной программы. Мне было интересно, есть ли способ завершить работу программы после поиска первого решения? Это занимает слишком много времени, и возможное решение будет хорошо работать для моих целей.

Answer 1

Если вы используете PuLP (другая библиотека python, такая как cvxopt), чтобы вызвать glpk для решения MIP, есть один параметр, называемый maxtime. Если вы установили maxtime=1, то что будет делать решатель, прекратите поиск (почти) сразу после нахождения первого решения. Уверен, что cvxopt должен иметь некоторый схожий параметр для glpk, поскольку либо PuLP, либо cvxopt - это всего лишь оболочка этих решателей.

Скопируйте вставить описание параметра maxtime в Xpress, который является еще одним решателем, но я думаю, что glpk должен иметь нечто похожее, которое вам может понадобиться для его выяснения.

The maximum time in seconds that the Optimizer will run before it terminates, including the problem setup time and solution time. For MIP problems, this is the total time taken to solve all the nodes. 

     0 = No time limit. 
     n > 0 = If an integer solution has been found, stop MIP search after n seconds, otherwise continue until an integer solution is finally found. 
     n < 0 = Stop in LP or MIP search after -n seconds. 

Answer 2

Если я вас правильно понимаю, вас интересует только допустимое решение?

Тогда этого должно быть достаточно, чтобы установить целевую функцию на ноль.

Вот Wikipedia example для целочисленного линейного программирования, и следующий код Python возвращает допустимое решение:

import cvxopt 
import cvxopt.glpk 

# original program maximizing the second variable 
# c=cvxopt.matrix([0,-1],tc='d') 

# modified program returning only a feasible solution 
c=cvxopt.matrix([0,0],tc='d') 

G=cvxopt.matrix([[-1,1],[3,2],[2,3],[-1,0],[0,-1]],tc='d') 
h=cvxopt.matrix([1,12,12,0,0],tc='d') 
(status, x)=cvxopt.glpk.ilp(c,G.T,h,I=set([0,1])) 
print('status',status) 
print('variables',x[0],x[1]) 
print('objective',sum(c.T*x))