Целочисленная переменная решения в нелинейном программировании - PullRequest
Новая
       49

Целочисленная переменная решения в нелинейном программировании

0 голосов
/ 20 октября 2018

Я бы хотел максимизировать частное двух linear функций.Я хотел бы, чтобы мои переменные решения были здесь Binary, то есть они должны быть integers и принимать значения только 0 и 1.

Я хотел бы знать, как я могу этого достичь?Я пытаюсь использовать алгоритм типа SLSQP, и я посмотрел на scipy, но, к сожалению, он не ограничивает значения переменных решения бинарными и целочисленными.

Кто-нибудь знает библиотеку спростой для понимания интерфейс, который я могу использовать для достижения этой цели?Или, если есть какой-либо способ достичь этого через scipy сам.Я прочитал этот вопрос: Ограничить scipy.optimize.minimize целочисленными значениями

Но здесь из трех предложенных решений я не думаю, что какое-либо из них является эффективным.Было бы очень полезно, если бы была оказана помощь.

Ответы [ 2 ]

0 голосов
/ 21 октября 2018

Я полностью делаю это не по назначению ... но вот как я это сделаю с mystic. 

>>> equations = """
... 3.*x0 + 5.*x1 + 7.*x2 + 9.*x3 = 1.*x0 + 2.*x1 + 3.*x3
... """
>>> bounds = [(0,None)]*4
>>>
>>> def objective(x):
...   return x[0]**2 + 2*x[1] - 2*x[2] - x[3]**2
... 
>>> from mystic.symbolic import generate_penalty, generate_conditions
>>> pf = generate_penalty(generate_conditions(equations))
>>> from mystic.constraints import integers
>>> 
>>> @integers()
... def round(x):
...   return x
... 
>>> from mystic.solvers import diffev2
>>> result = diffev2(objective, x0=bounds, bounds=bounds, penalty=pf, constraints=round, npop=20, gtol=50, disp=True, full_output=True)
Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 121
         Function evaluations: 2440
>>> result[0]
array([0., 0., 0., 0.])

Теперь немного изменим уравнения ... 

>>> equations = """
... 3.*x0 + 5.*x1 + 7.*x2 + 9.*x3 = 5 + 1.*x0 + 2.*x1 + 3.*x3
... """
>>> pf = generate_penalty(generate_conditions(equations))
>>> result = diffev2(objective, x0=bounds, bounds=bounds, penalty=pf, constraints=round, npop=20, gtol=50, disp=True, full_output=True)
Optimization terminated successfully.
         Current function value: 3.000000
         Iterations: 102
         Function evaluations: 2060
>>> result[0]
array([1., 1., 0., 0.])

Если вы хотите, чтобы двоичные переменные вместо целых чисел, вы можете либо использовать bounds = [(0,1)]*4, либо заменить @integers() на @discrete([0.0, 1.0]).

Хотя приведенное выше не слишком интересно для результатаЕсть несколько более продуманных примеров глобальной оптимизации с целочисленным программированием и обобщенными ограничениями на GitHub от Mystic: https://github.com/uqfoundation/mystic/blob/master/examples2/integer_programming.py https://github.com/uqfoundation/mystic/blob/master/examples2/olympic.py

0 голосов
/ 20 октября 2018

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

import numpy as np

def maximize(numer, denom):
    """ 
    Function that maximizes an expression on the form

    a[0]*x[0] + a[1]*x[1] + ... + a[n-1]*x[n-1]
    -----------------------------------------
    b[0]*x[0] + b[1]*x[1] + ... + b[n-1]*x[n-1]

    where a[i] >= 0, b[i] >= 0, x[i] in [0,1] for 0 < i < n (non-negativity)
    and
    a[0] >= 0, b[0] > 0, x[0] = 1 (no division by zero)
    """

    ratios = numer / denom
    indices, ratios = zip(*sorted(enumerate(ratios), key = lambda x: - x[1]))
    decision = np.zeros_like(numer) 
    decision[0] = 1 # the bias is always enabled
    best_value = np.sum(decision * numer) / np.sum(decision * denom)
    for index, ratio in zip(indices, ratios):
        if index == 0:
            continue
        if ratio > best_value:
            decision[index] = 1 
            best_value = np.sum(decision * numer) / np.sum(decision * denom)
        else:
            # no more ratios can increase the cumulative ratio
            break  
    return decision

и вот пример использования 

if __name__ == "__main__":
    numer = np.array([1, 3, 4, 6])
    denom = np.array([1, 2, 2, 3])
    print("Input: {} / {}".format(",".join([str(x) for x in numer]), ",".join([str(x) for x in denom])))
    decision = maximize(numer, denom)
    print("Decision: {}".format(decision))
    print("Objective: {}".format(np.sum(decision * numer) / np.sum(decision * denom)))
...