Python 线性规划 - 如何将变量约束为整数

Question

我想通过购买一定数量的彩票来最大化赢得抽奖的概率。为此，我写了下面的代码

import numpy as np
import math as mt
from scipy.optimize import minimize
from pulp import *

def objective(tickets, winners = 500, losers = 2500, cost_of_ticket = 40, winning_amt = 1000):

    Pwin = 1 - mt.factorial(losers)//mt.factorial(losers - tickets)*mt.factorial(winners+losers-tickets)/mt.factorial(winners+losers)
    Ewin = Pwin*(winning_amt - cost_of_ticket*tickets)

    return Ewin


# declare your variables
tickets = LpVariable("tickets", range(0, 10))   # 0<= tickets <= 10

prob = LpProblem("problem", LpMaximize)

#define the objective
prob += objective(tickets)

# solve the problem
status = prob.solve(GLPK(msg=0))
LpStatus[status]

# print the results
value(tickets)

问题似乎是传递给 objective 函数的票数不是整数（然后阶乘函数失败）。谁能建议我应该如何确保票证仅限于正整数值？

检查的答案应该是 8。我可以通过手动调用 objective 函数并检查来做到这一点。

Answer 1

你的objective真是

 ExpWin(t) = choose(N,t)*(A-C*t)

其中 t 是整数变量，N、A、C 是常量。这是一个非线性函数，因此线性 MIP 求解器无法处理。

对于这个问题来说它很愚蠢，但通常我们可以将其线性化。引入二元变量 x(i) 为：

x(i) = 1 if tickets=i
       0 otherwise

这可以通过

强制执行

sum(i,x(i)) = 1
sum(i,i*x(i)) = tickets

这仅在可变票证的范围较小（在您的情况下为 10）时才有意义。现在我们可以预先计算一个常量数组 w(i)，如果票数是 i，它就是预期的赢奖。现在 objective 可以看起来像：

max sum(i, w(i)*x(i))

现在是线性的。

无论如何，远离代码并用数学写下问题总是一个好主意。这可以帮助您以不同的方式思考问题。

Answer 2

您可以在定义变量时将其限制为整数：

tickets = LpVariable("tickets", range(0, 10), cat='Integer') # 0<= tickets <= 10

根据 sascha 的评论，对此进行了解释 here

Python 线性规划 - 如何将变量约束为整数

Python linear programming - how to constrain a variable to be an integer

python

constraints

pulp