线性规划：在变量偏离最优值时添加惩罚，但单一数值除外。

huangapple
go评论82阅读模式
英文:

Linear Programming: Add penalty as variable diverge from optimal value, with single value exception

问题

我试图在我的线性规划项目中引入一个惩罚约束，求解器正在寻找x的最优值（整数值），在其他约束条件中，我希望当x偏离最优值时，对x进行惩罚。

我将这个约束添加为：

  1. self.prob += x - optimal_size <= _SP
  2. self.prob += x - optimal_size >= -_SP

将_SP添加到我的目标函数作为惩罚：

  1. objective += other_values - 0.1 * SP

在这种情况下，optimal_size等于3，但我也希望在x等于0时不应用这个惩罚。你有什么建议可以实现这一点的好方法吗？

英文:

I am trying to have a penalty constraint in my LP project, the solver is looking for an optimal value of x (integer value), among other constraints, I want x to be penalized the more it diverges from an optimal value.

I added this constraint as

  1. self.prob += x - optimal_size &lt;= _SP
  2. self.prob += x - optimal_size &gt;= -_SP

Adding _SP as penalty to my objective function

  1. objective += other_values - 0.1 * SP

In this case, optimal_size is == 3, but I'd also like however that this penalty would not be applied if x == 0. Do you have a suggestion on what would be a nice way to do it?

答案1

得分: 0

我的方法如下：

  1. 计算x与optimal_x_fixed的偏差，存储在变量divergence_x_from_fixed_raw中
  2. 取上述偏差的绝对值，存储在变量divergence_x_from_fixed_absolute中
  3. 创建一个布尔变量：impose_penalty_bool，以突出以下情况：
    • 如果x == 0 => impose_penalty_bool == 0
    • 如果x >= 1 => impose_penalty_bool == 1
  4. 创建一个整数变量final_penalty_value，以存储impose_penalty_bool与divergence_x_from_fixed_absolute的乘积
  5. 根据第4步的效果：
    • 如果x == 0 => impose_penalty_bool == 0 => final_penalty_value == 0
    • 如果x == optimal_x_fixed => impose_penalty_bool == 1 => final_penalty_value == 0（因为偏差的绝对值等于0）
    • 如果x != 0 且偏差的绝对值 > 0 => impose_penalty_bool = 1 => final_penalty_value > 0

我已经使用Google OR-Tools的线性求解器实现了上述逻辑，但以下实现也适用于任何其他线性求解器：

  1. from ortools.linear_solver import pywraplp
  3. solver = pywraplp.Solver("penalty_obj", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)
  5. # 以下值在给定迭代中是固定的，但可以在后续运行中更改
  6. optimal_x_fixed = 3
  8. # 决策变量
  9. x = solver.IntVar(lb=-10, ub=10, name="x")
  11. # 由于我们（我）不知道目标函数，为了测试逻辑，我固定了x的值
  12. x.SetBounds(lb=3, ub=3)
  14. # 绝对值是非线性函数，我们需要线性化它
  16. # ------------------- 步骤 1 和 2，开始 ----------------------#
  17. # 在这里，我们计算“x”与“optimal_x_fixed”之间的偏差
  18. divergence_x_from_fixed_raw = solver.IntVar(lb=-20, ub=20, name="divergence_raw")
  19. solver.Add(divergence_x_from_fixed_raw == optimal_x_fixed - x)
  21. # 创建一个变量，它将存储偏差的绝对值
  22. divergence_x_from_fixed_absolute = solver.IntVar(lb=0, ub=20, name="divergence_abs")
  24. # 创建正部分和负部分
  25. # 思路是在任何时候只有一个部分可以具有非零值
  26. divergence_x_from_fixed_pos = solver.IntVar(lb=0, ub=20, name="divergence_pos")
  27. divergence_x_from_fixed_neg = solver.IntVar(lb=0, ub=20, name="divergence_neg")
  28. divergence_x_binary = solver.BoolVar("")
  30. solver.Add(divergence_x_from_fixed_raw == divergence_x_from_fixed_pos - divergence_x_from_fixed_neg)
  32. # 以下约束确保只有正部分或负部分可以具有非零值
  33. # 100 是大M（大的正数）
  34. solver.Add(divergence_x_from_fixed_pos <= 100 * divergence_x_binary)
  35. solver.Add(divergence_x_from_fixed_neg <= 100 * (1 - divergence_x_binary))
  37. solver.Add(divergence_x_from_fixed_absolute == divergence_x_from_fixed_pos + divergence_x_from_fixed_neg)
  39. # ------------------- 步骤 1 和 2，结束 ----------------------#
  41. # ------------------- 步骤 3，开始 ----------------------#
  43. # 接下来，我们要创建一个布尔变量：“impose_penalty_bool”
  44. # 我们希望的是，如果 x == 0，则 impose_penalty_bool == 0：
  45. # 如果 x >= 1，则 mpose_penalty_bool == 1
  46. # 但是，如果 x == 3，那么我们也不希望有任何惩罚，
  47. # 这将解决下一个问题
  49. impose_penalty_bool = solver.BoolVar("")
  51. # 100 是 x 的上界
  52. # 以下 2 个约束实现了：
  53. # 如果 x == 0，则 impose_penalty_bool == 0：
  54. # 如果 x >= 1，则 mpose_penalty_bool == 1
  55. solver.Add(x - (100 * impose_penalty_bool) <= 0)
  56. solver.Add(x - impose_penalty_bool >= 0)
  58. # ------------------- 步骤 3，结束 ----------------------#
  60. # ------------------- 步骤 4，开始 ----------------------#
  62. # 最后，我们要做的是将“impose_penalty_bool”与之前计算的“optimal_x_fixed = 3”的偏差的绝对值相乘
  63. # 效果将是：
  65. # 如果 x == 0 => impose_penalty_bool == 0 => final_penalty_value == 0
  66. # 如果 x == optimal_x_fixed => impose_penalty_bool = 1 => final_penalty_value == 0
  67. # (因为偏差的绝对值 == 0)
  68. # 如果 x != 0 且偏差的绝对值 > 0 => impose_penalty_bool = 1 => final_penalty_value > 0
  70. # 用 impose_penalty_bool 乘以 divergence_x_from_fixed_absolute
  71. final_penalty_value = solver.IntVar(lb=0, ub=20, name="final_penalty")
  72. # u 是 divergence_x_from_fixed_absolute 的上界。 u = 30（假设）
  73. solver.Add(final_penalty_value <= 30 * impose_penalty_bool)
  74. solver.Add(final_penalty_value <= divergence_x_from_fixed_absolute)
  75. solver.Add(final_penalty_value >= divergence_x_from_fixed_absolute - 30 * (1 - impose_penalty_bool))
  77. # 通过上述操作，我们线性化了二进制变量：impose_penalty_bool 和整数变量：divergence_x_from_fixed_absolute
  79. # 通常，如果 x1 是二进制变量，x2 是连续/整数变量
  80. # u 是 x2 的上界。引入一个 y 变量来保存乘积
  81. # 引入以下约束
  82. # y <= u * x1
  83. # y <= x2
  84. # y <= x2 - u * (1 - x1)
  85. # y >= 0
  87. # ------------------- 步骤 4，结束 ----------------------#
  89. # 定义目标函数
  91. obj_function = x + final_penalty_value
  93. solver.Maximize(obj_function)  #
  95. <details>
  96. <summary>英文:</summary>
  98. My approach is as follows :
  99. 1) calculate the divergence of `x` from `optimal_x_fixed` in variable : `divergence_x_from_fixed_raw`
  100. 2) take the absolute of the above divergence in variable : `divergence_x_from_fixed_absolute`
  101. 3) create a boolean variable : `impose_penalty_bool` to highlight that: &lt;br /&gt;
  102.          if `x == 0` =&gt; `impose_penalty_bool == 0` &lt;br /&gt;
  103.          if `x &gt;= 1` =&gt; `impose_penalty_bool == 1` &lt;br /&gt;
  104. 4) create an integer variable `final_penalty_value` to store the multiplication of `impose_penalty_bool` and `divergence_x_from_fixed_absolute`
  105. 5) effect from 4) will be &lt;br /&gt;
  106.         if `x == 0` =&gt; `impose_penalty_bool == 0` =&gt; `final_penalty_value == 0` &lt;br /&gt;
  107.         if `x == optimal_x_fixed` =&gt; `impose_penalty_bool == 1` =&gt; `final_penalty_value == 0` (beacuse absolute of deviance == 0) &lt;br /&gt;
  108.         if `x != 0` and `absolute of deviance &gt; 0` =&gt; `impose_penalty_bool = 1` =&gt; `final_penalty_value &gt; 0`
  111. I have used Google-ortool&#39;s linear solver, but below implementation can be used with any other linear solver:

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver("penalty_obj",pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

below value is fixed for a given iteration, but can be changed in subsequent run

optimal_x_fixed = 3

decision variable

x = solver.IntVar(lb = -10, ub = 10, name = "x")

since we (I) dont know the objective function, in order to test the logic,

I have fixed the value of x

x.SetBounds(lb = 3, ub = 3)

The absolute value is a non-linear function. We will have to linearise it

------------------- STEPS 1 and 2, START ----------------------#

here we calculate the divergence between "x" and the "optimal_x_fixed"

divergence_x_from_fixed_raw = solver.IntVar(lb = -20, ub = 20, name = "divergence_raw")
solver.Add(divergence_x_from_fixed_raw == optimal_x_fixed - x)

create a variable which will store the absolute value of the divergence

divergence_x_from_fixed_absolute = solver.IntVar(lb = 0, ub = 20, name = "divergence_abs")

create a positive and negative part

idea is only one of the parts can have a value other than zero at any time

divergence_x_from_fixed_pos = solver.IntVar(lb = 0, ub = 20, name = "divergence_pos")
divergence_x_from_fixed_neg = solver.IntVar(lb = 0, ub = 20, name = "divergence_neg")
divergence_x_binary = solver.BoolVar("")

solver.Add(divergence_x_from_fixed_raw == divergence_x_from_fixed_pos - divergence_x_from_fixed_neg)

below constraint ensure that only positive or negative part takes value other than zero

100 is big_M

solver.Add(divergence_x_from_fixed_pos <= 100 * divergence_x_binary)
solver.Add(divergence_x_from_fixed_neg <= 100 * (1 - divergence_x_binary))

solver.Add(divergence_x_from_fixed_absolute == divergence_x_from_fixed_pos + divergence_x_from_fixed_neg)

------------------- STEPS 1 and 2, END ----------------------#

------------------- STEPS 3, START ----------------------#

next we want to create a boolean variable : "impose_penalty_bool"

what we want is if x == 0, then impose_penalty_bool == 0

if x >= 1, then mpose_penalty_bool == 1

however, if x == 3, then also we dont want any penalty,

this will tackle next

impose_penalty_bool = solver.BoolVar("")

100 is upper bound on x

below 2 constraints achieve:

  1. # if x == 0, then impose_penalty_bool == 0:
  2. # if x &gt;= 1, then mpose_penalty_bool == 1

solver.Add(x - (100 * impose_penalty_bool) <= 0)
solver.Add(x - impose_penalty_bool >= 0)

------------------- STEPS 3, END ----------------------#

------------------- STEPS 4, START ----------------------#

finally what we want to do is multiply "impose_penalty_bool"

with the absolute of deviance from "optimal_x_fixed = 3" we calculated earlier

the effect will be:

  1. # if x == 0 =&gt; impose_penalty_bool == 0 =&gt; final_penalty_value == 0
  2. # if x == optimal_x_fixed =&gt; impose_penalty_bool = 1 =&gt; final_penalty_value == 0
  3. # (beacuse absolute of deviance == 0)
  4. # if x != 0 and absolute of deviance &gt; 0 =&gt; impose_penalty_bool = 1 =&gt; final_penalty_value &gt; 0

multiply impose_penalty_bool with divergence_x_from_fixed_absolute

final_penalty_value = solver.IntVar(lb = 0, ub = 20, name = "final_penalty")

u is the upper bound on divergence_x_from_fixed_absolute. u = 30 (say)

solver.Add(final_penalty_value <= 30 * impose_penalty_bool)
solver.Add(final_penalty_value <= divergence_x_from_fixed_absolute)
solver.Add(final_penalty_value >= divergence_x_from_fixed_absolute - 30 * (1 - impose_penalty_bool))

by doing above we linearise the product of binary : impose_penalty_bool # and the integer variable : divergence_x_from_fixed_absolute

generally, if x1 is binary, and x2 is continuous / integer

u is upper bound on x2. introduce a y variable to hold the product

impose following constraints

y <= u * x1

y <= x2

y <= x2 - u * (1 - x1)

y >= 0

------------------- STEPS 4, END ----------------------#

DEFINE OBJECTIVE FUNCTION

obj_function = x + final_penalty_value

solver.Maximize(obj_function) # or minimise, depends
solver.Solve()

solver.Objective().Value()

-----------------------------------

  2. I have checked with different values of `x`, outcome is on expected lines.
  3. final_penalty_value == 0 if x == 0 or x == 3 (equal to fixed value)
  4. for x != 3 or x != 0, final_penalty_value &gt; 0
  5. </details>

huangapple
  • 本文由 发表于 2023年6月19日 16:53:47
  • 转载请务必保留本文链接：https://go.coder-hub.com/76505079.html
  • linear-programming
  • pulp
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定