0

我想最大化两个linear函数的商。我希望我的决策变量在Binary这里，即它们必须integers并且只能取值0和1。

我想知道我怎样才能做到这一点？我正在寻找使用类似的算法SLSQP并且我已经看过scipy但遗憾的是它并没有将决策变量的值限制为二进制和整数。

有谁知道一个具有易于理解的界面的库，我可以使用它来实现这一点？或者是否有任何方法可以通过scipy自身实现这一目标。我读过这个问题：Restrict scipy.optimize.minimize to integer values

但是在提供的三种解决方案中，我认为它们中的任何一种都不是有效的。如果可以提供任何帮助，那将非常有帮助。

4

2 回答 2

0

我完全是在即兴做这件事……但这就是我的做法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]).

虽然上面的结果不太有趣，但在 mystic 的 GitHub 上，有一些经过深思熟虑的整数规划和广义约束的全局优化示例： https ://github.com/uqfoundation/mystic/blob/master/examples2 /integer_programming.py https://github.com/uqfoundation/mystic/blob/master/examples2/olympic.py

于 2018-10-21T14:36:46.603 回答
0

由于您没有任何约束，除了变量应该是二进制的，因此最大化非常简单。您可以根据分子和分母中相应系数的比率对决策变量进行排序。假设所有系数都是非负的，并且分子和分母存在偏差（以避免被零除），您可以使用下面的实现。

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)))
于 2018-10-20T13:57:11.023 回答