问题

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

我将这个约束添加为：

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

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

objective += other_values - 0.1 * SP

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

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

objective += other_values - 0.1 * SP

答案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的线性求解器实现了上述逻辑，但以下实现也适用于任何其他线性求解器：

from ortools.linear_solver import pywraplp

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

# 以下值在给定迭代中是固定的，但可以在后续运行中更改
optimal_x_fixed = 3

# 决策变量
x = solver.IntVar(lb=-10, ub=10, name="x")

# 由于我们（我）不知道目标函数，为了测试逻辑，我固定了x的值
x.SetBounds(lb=3, ub=3)

# 绝对值是非线性函数，我们需要线性化它

# ------------------- 步骤 1 和 2，开始 ----------------------#
# 在这里，我们计算“x”与“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)

# 创建一个变量，它将存储偏差的绝对值
divergence_x_from_fixed_absolute = solver.IntVar(lb=0, ub=20, name="divergence_abs")

# 创建正部分和负部分
# 思路是在任何时候只有一个部分可以具有非零值
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)

# 以下约束确保只有正部分或负部分可以具有非零值
# 100 是大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)

# ------------------- 步骤 1 和 2，结束 ----------------------#

# ------------------- 步骤 3，开始 ----------------------#

# 接下来，我们要创建一个布尔变量：“impose_penalty_bool”
# 我们希望的是，如果 x == 0，则 impose_penalty_bool == 0：
# 如果 x >= 1，则 mpose_penalty_bool == 1
# 但是，如果 x == 3，那么我们也不希望有任何惩罚，
# 这将解决下一个问题

impose_penalty_bool = solver.BoolVar("")

# 100 是 x 的上界
# 以下 2 个约束实现了：
# 如果 x == 0，则 impose_penalty_bool == 0：
# 如果 x >= 1，则 mpose_penalty_bool == 1
solver.Add(x - (100 * impose_penalty_bool) <= 0)
solver.Add(x - impose_penalty_bool >= 0)

# ------------------- 步骤 3，结束 ----------------------#

# ------------------- 步骤 4，开始 ----------------------#

# 最后，我们要做的是将“impose_penalty_bool”与之前计算的“optimal_x_fixed = 3”的偏差的绝对值相乘
# 效果将是：

# 如果 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

# 用 impose_penalty_bool 乘以 divergence_x_from_fixed_absolute
final_penalty_value = solver.IntVar(lb=0, ub=20, name="final_penalty")
# u 是 divergence_x_from_fixed_absolute 的上界。 u = 30（假设）
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))

# 通过上述操作，我们线性化了二进制变量：impose_penalty_bool 和整数变量：divergence_x_from_fixed_absolute

# 通常，如果 x1 是二进制变量，x2 是连续/整数变量
# u 是 x2 的上界。引入一个 y 变量来保存乘积
# 引入以下约束
# y <= u * x1
# y <= x2
# y <= x2 - u * (1 - x1)
# y >= 0

# ------------------- 步骤 4，结束 ----------------------#

# 定义目标函数

obj_function = x + final_penalty_value

solver.Maximize(obj_function)  #

<details>
<summary>英文:</summary>

My approach is as follows :
1) calculate the divergence of `x` from `optimal_x_fixed` in variable : `divergence_x_from_fixed_raw`
2) take the absolute of the above divergence in variable : `divergence_x_from_fixed_absolute`
3) create a boolean variable : `impose_penalty_bool` to highlight that: &lt;br /&gt;
         if `x == 0` =&gt; `impose_penalty_bool == 0` &lt;br /&gt;
         if `x &gt;= 1` =&gt; `impose_penalty_bool == 1` &lt;br /&gt;
4) create an integer variable `final_penalty_value` to store the multiplication of `impose_penalty_bool` and `divergence_x_from_fixed_absolute`
5) effect from 4) will be &lt;br /&gt;
        if `x == 0` =&gt; `impose_penalty_bool == 0` =&gt; `final_penalty_value == 0` &lt;br /&gt;
        if `x == optimal_x_fixed` =&gt; `impose_penalty_bool == 1` =&gt; `final_penalty_value == 0` (beacuse absolute of deviance == 0) &lt;br /&gt;
        if `x != 0` and `absolute of deviance &gt; 0` =&gt; `impose_penalty_bool = 1` =&gt; `final_penalty_value &gt; 0`


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:

# if x == 0, then impose_penalty_bool == 0:
# if x >= 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:

# if x == 0 => impose_penalty_bool == 0 => final_penalty_value == 0
# if x == optimal_x_fixed => impose_penalty_bool = 1 => final_penalty_value == 0
# (beacuse absolute of deviance == 0)
# if x != 0 and absolute of deviance > 0 => impose_penalty_bool = 1 => final_penalty_value > 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()

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

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