Gurobi MIP: ослабление ограничений, приводящее к худшему оптимальному решению - PullRequest
Новая
       29

Gurobi MIP: ослабление ограничений, приводящее к худшему оптимальному решению

0 голосов
/ 28 апреля 2020

У меня довольно простая проблема MIP: учитывая набор чисел, выберите n из тех чисел, которые должны суммироваться, чтобы быть выше заданного порога. Минимизируйте, насколько эта сумма превышает этот порог.

Код следующим образом: 

colors = [...]
threshold = 9851000000000.0 / 1e12
n = 36

for i in range(1):
    # initialize
    m = Model("HarvestProblem")

    # initialize variables
    cs = []
    for i in range(len(colors)):
        name = "cs" + str(i).zfill(5)
        cs.append(m.addVar(vtype=GRB.BINARY, name=name))

    # set objective
    m.setObjective(sum([colors[i] * cs[i] for i in range(len(colors))]), GRB.MINIMIZE)

    # set constraints
    m.addConstr(quicksum([colors[i] * cs[i] for i in range(len(colors))]) >= threshold)
    m.addConstr(quicksum(cs) == n)

    m.optimize()

Это, gurobi легко решается. Возникла мысль: если я разрешаю выбирать меньше n, то есть больше вариантов, которые могут привести к более оптимальному результату. Однако, когда я делаю это (таким образом изменяя второе ограничение), оптимальное решение, которое я получаю, хуже. Это я нахожу странным, так как оригинальное решение все еще возможно. Любые подсказки?

Исходный результат: 

Solution count 1: 9.85112 

Optimal solution found (tolerance 1.00e-04)
Best objective 9.851118387317e+00, best bound 9.851000000000e+00, gap 0.0012%

Новый результат: 

Solution count 1: 9.85121 

Optimal solution found (tolerance 1.00e-04)
Best objective 9.851213112957e+00, best bound 9.851000000000e+00, gap 0.0022%
...