Есть ли удобный способ express непрерывного расслабления MIP с использованием cvxpy? - PullRequest
Новая
       4

Есть ли удобный способ express непрерывного расслабления MIP с использованием cvxpy?

1 голос
/ 07 февраля 2020

Я хочу решить (выпуклую) смешанную целочисленную программу, а также ее непрерывную релаксацию с помощью cvxpy. Есть ли способ использовать одну и ту же реализацию цели и ограничений для обоих расчетов?

В качестве примера рассмотрим примерную проблему MIP с веб-сайта cvxpy с некоторым добавленным ограничением 'x [0]> = 2': 

np.random.seed(0)
m, n= 40, 25
A = np.random.rand(m, n)
b = np.random.randn(m)
# Construct a CVXPY problem
x = cp.Variable(n, integer=True) # x is an integer variable
obj = cp.sum_squares(A@x - b)
objective = cp.Minimize(obj)
constraint = [x[0] >= 2]
prob = cp.Problem(objective, constraint)
prob.solve()
print("The optimal value is", prob.value)
print("A solution x is")
print(x.value)

x = cp.Variable(n) # Now, x is no longer an integer variable but continuous
obj = cp.sum_squares(A@x - b) # I want to leave out this line (1)
constraint = [x[0] >= 2] # I want to leave out this line (2)
objective = cp.Minimize(obj)
prob = cp.Problem(objective, constraint)
prob.solve()
print("The optimal value is", prob.value)
print("A solution x is")
print(x.value)

При выходе из строки ( 2) проблема решена без ограничений. При выходе из строки (1) решается смешанная целочисленная задача (поэтому замена x на непрерывную переменную не имела никакого эффекта).

Я хочу избежать повторной реализации целевой функции и ограничений, поскольку пропущенное копирование и вставка может привести к странным, трудно обнаруживаемым ошибкам. Спасибо за вашу помощь!

Редактировать: Спасибо, Саша, за ваш ответ. Вы правы, аутсорсинг моделестроения решает проблему. Так что 

class ModelBuilder:
    m, n = 40, 25
    A = np.random.rand(m, n)
    b = np.random.randn(m)
    def __init__(self, solve_continuous):
        np.random.seed(0)
        if solve_continuous:
            self.x = cp.Variable(self.n)
        else:
            self.x = cp.Variable(self.n, integer=True)
    @staticmethod
    def constraint_func(x):
        return [x[0] >= 2]
    def objective_func(self, x):
        return cp.sum_squares(self.A@x - self.b)
    def build_problem(self):
        objective = cp.Minimize(self.objective_func(self.x))
        constraint = self.constraint_func(self.x)
        return cp.Problem(objective, constraint)

# Construct and solve mixed integer problem
build_cont_model = False
MIP_Model = ModelBuilder(build_cont_model)
MIP_problem = MIP_Model.build_problem()
MIP_problem.solve()
print("The optimal value is", MIP_problem.value)
print("A solution x is")
print(MIP_Model.x.value)

# Construct and solve continuous problem
build_cont_model = True
Cont_Model = ModelBuilder(build_cont_model)
Cont_problem = Cont_Model.build_problem()
Cont_problem.solve()
print("The optimal value is", Cont_problem.value)
print("A solution x is")
print(Cont_Model.x.value)

работает так, как ожидалось. Поскольку у меня не было этой простой идеи, это показывает, что я еще не понимаю концепции применения cvxpy.Variable к выражению.

В моей первой попытке я определил переменную x и использовал ее при определении obj. Затем я изменил значение x (за одну строку до (1)). Я думал, что obj связан с x указателем или чем-то подобным, так что это также изменит его поведение. Очевидно, это не тот случай.

Знаете ли вы какие-либо ресурсы, которые могли бы помочь мне понять это поведение? Или это очевидно для всех, кто знаком с Python? Тогда где я могу узнать об этом?

...