параметризованный вектор с PySCIPopt - PullRequest
Новая
       86

параметризованный вектор с PySCIPopt

5 голосов
/ 11 июля 2019

Я пытаюсь использовать PySCIPopt для решения традиционной проблемы типа Ax-b +. У меня много значений b, и мне нужно запустить оптимизатор для каждого из них. Как я могу использовать настройки? Второй вопрос, что эквивалентно norm в PySCIPopt? Или как правильно вести Ax-b как можно ближе к нулю? Увидеть ??? отметки ниже 

import numpy as np
from pyscipopt import Model, quicksum

def make_program():
    A = ... load constant master matrix ...
    model = Model('Match_to_Master')
    x = []
    y = []
    for i in range(A.shape[1]):
        x.append(model.addVar(vtype='C', lb=0.0, ub=4.0, name='x(%s)' % i))
        y.append(model.addVar(vtype='B', name='y(%s)' % i))
        model.addCons(x[i] <= y[i]*4)
    for i in range(0, A.shape[1] - 20, 20):
       model.addCons(quicksum(y[i:i+20]) <= 1)

    #b = Parameter(A.shape[0], nonneg=True) ???
    model.setObjective(norm(A*x - b), sense='minimize') ???
    return b, x, model


def run_program(data, thresh=0.2):
    b, x, model = make_program()
    B = ... from data load matrix for analysis ...
    c = 0
    for column in B.T:
        b.value = column   ???
        model.optimize()  # reuse previous x values as starting point
        x.value[x.value < thresh] = 0.0
        for i in range(0, x.value.size - 20, 20):
            sum = np.sum(x.value[i:i+20])
            if sum > 0.2:
                print('  hit at ', str(i//20), ' for column ', str(c))
        c += 1

1 Ответ

0 голосов
/ 15 июля 2019

Ну, я не думаю, что вы решаете традиционную проблему типа Ax - b.Традиционный тип - min | Ax - b | ^ 2.Для этого вам не нужен scip.

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

Тем не менее, вы можете использовать решение из предыдущего запуска.Используйте 

solution = model.createSol(None)

# for each nonzero variable
model.setSolVal(solution, var, val)

model.trySol(solution)

, чтобы создать решение, установить его значения и добавить его в модель.

Что касается минимизации нормы, как указывает sascha, вы можете минимизировать только полиэдральные нормы, скорее всегонорма 1 / инф.В первом случае вы можете использовать

min y_1 + ... + y_m + z_1 + ... + z_m

st A x + y - z = b

y, z> = 0

В последнем вы можете использовать

min d

st A x + y - z = b

y, z> = 0

d> = y_i, i = 1, ..., m

d> = z_i i = 1, ..., m

В любом случае это не поддерживается с помощью scip из коробки, поэтому вам придется самостоятельно добавлять соответствующие переменные / ограничения.

Редактировать:

Относительно2-норма: Во-первых, обратите внимание, что минимизация 2-нормы превращает задачу в смешанную целочисленную нелинейную программу (MINLP), в частности, в смешанную целочисленную квадратичную задачу (MIQP).Таким образом, проблему становится все труднее решить :) Я не знаю, подходит ли SCIP лучше всего в этом случае (я слышал хорошие вещи о Pajarito ).Тем не менее, SCIP может решать MINLP.

Чтобы смоделировать норму, вы должны заметить, что SCIP не поддерживает нелинейные цели, только нелинейные ограничения.Таким образом, модель должна быть

мин y_1 + ... + y_m

st (A x - b) ^ 2 - y <= 0 </p>

Вы должны быть в состояниидобавить произвольные нелинейные ограничения через model.addConst(...) На основе степени выражения, pyscipopt будет делать правильные вещи .В случае ограничения степени 2, например 

model.addCons(x[i]*y[i] <= 0)

, это означает добавление квадратичного ограничения.

Обратите внимание, что это сведет к минимуму квадратную норму вместо нормы.Вы получите правильное решение, но значение цели будет выключено.

Кроме того, я думаю, что это поможет / может потребоваться для компиляции scip с включенной поддержкой Ipopt.Ipopt является решателем для нелинейных программ (НЛП), которые являются ослаблениями MINLP.

...