英文:
Express logical constraints : one constraint implies another in linear programming (open source solver)
问题
How to express the following in linear programming with open-source solvers:
2*x + 3*y >= 15 ==> m + n <= 5
In open-source solvers, you can use the following syntax:
2*x + 3*y >= 15
m + n <= 5
This represents the same constraint without the need for if-then
notation, as open-source solvers typically allow you to directly specify linear constraints like this.
英文:
How can I express the following in linear programming:
2*x + 3*y >= 15 ==> m + n <= 5
x, y, m and n are decision variables (continuous or integer) with relevant upper and lower bounds
I know with CPLEX (OPL and with python API), we can write if-then
constraints like :
2*x + 3*y >= 15 => m + n <= 5 (OPL)
model.add_if_then(2*x + 3*y >= 15, m + n <= 5) [python API, docplex]
But how to express above in an open source solver ?
答案1
得分: 1
使用指示约束,您可以将逻辑建模如下:
2*x + 3*y >= 15 ==> w == 1
w == 1 ==> m + n <= 5
其中,w是一个二进制变量。指示约束通常(至少在Gurobi中)的形式是:如果二进制变量(这里是 w
)为真,则将强制满足线性约束。因此,在Gurobi中,您需要表达以下关系:
2*x + 3*y >= 15 ==> w == 1
以及其逻辑的反命题:
w == 0 ==> 2*x + 3*y < 15
数学规划框架中不允许严格不等式,但我们可以使用某个小的 epsilon > 0
来近似这个约束。请注意,如果所有变量都是整数,我们可以使用 epsilon = 1
。因此最终得到:
w == 0 ==> 2*x + 3*y < 15 - epsilon
w == 1 ==> m + n <= 5
在Gurobi中的实现如下:
model.addGenConstrIndicator(w, 0, 2*x + 3*y <= 15 - epsilon)
model.addGenConstrIndicator(w, 1, m + n <= 5)
对于开源求解器,您可以使用 big M
来表达以下内容:
2*x + 3*y >= 15 ==> w == 1
实现:
a*x - (M + e) * w <= b - e
a、x 表示系数和变量
e(读作:epsilon)是一个小的容忍值,超过这个值,我们将视约束为被打破。
如果变量是整数,我们可以取 e = 1
M(big_M)是 2*x + 3*y - 15 的上界
b 是约束的右手边
以及:
w == 1 ==> m + n <= 5
实现:
a*x - b <= M * (1 - w)
M(big_M)是 m + n - 5 的上界
在Google OR-Tools中的线性求解器(Python API)中的实现如下:
# 请注意,代码中可能存在格式化问题,需要进一步验证。
这个实现假设了一些变量的上下界,并设置了目标函数以最大化。在解决问题后,您可以通过查询变量的解来获取结果。
英文:
Using indicator constraints, you can model the logic as follows:
2*x + 3*y >= 15 ==> w == 1
w == 1 ==> m + n <= 5
w is a binary variable
indicator are generally (at least in Gurobi) of the form : if binary variable (here w
) is true, then that would force the linear constraint to be satisfied. So in Gurobi, you would have to express the following :
2*x + 3*y >= 15 ==> w == 1
with its logical contra-positive i.e.
w == 0 ==> 2*x + 3*y < 15
Strict inequalities aren't allowed in a math programming framework, but we can closely approximate this constraint with 2*x + 3*y <= 15 - epsilon
for some small epsilon > 0
. Note that we can use epsilon = 1
if all variables are integers.
So finally:
w == 0 ==> 2*x + 3*y <= 15 - epsilon
w == 1 ==> m + n <= 5
In Gurobi :
model.addGenConstrIndicator(w, 0, 2*x + 3*y <= 15 - epsilon)
model.addGenConstrIndicator(w, 1, m + n <= 5)
I am not sure whether indicator constraints are supported in open source solvers.
For open source solvers, however, you can use big M
to express following:
2*x + 3*y >= 15 ==> w == 1
implementation:
a*x - (M + e) * w <= b - e
a, x represent coefficients and variables
e (read: epsilon) is some small tolerance value beyond which we will
regard the constraint as having been broken.
incase variables are integers, we can take e = 1
M (big_M) is the upper bound on 2*x + 3*y - 15
b is the RHS of the constraint
w == 1 ==> m + n <= 5
implementation:
a*x - b <= M * (1 - w)
M (big_M) is the upper bound on : m + n - 5
Below is the implementation in Google OR-Tools, linear solver (python API)
from ortools.linear_solver import pywraplp
s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)
e = 10e-5 #epsilon
x = s.NumVar(lb = 0, ub = 5, name = "x")
y = s.NumVar(lb = 0, ub = 5, name = "y")
m = s.NumVar(lb = 0, ub = 10, name = "x")
n = s.NumVar(lb = 0, ub = 10, name = "x")
# 2*x + 3*y >= 15 ==> m + n <= 5
# introduce w as a binary variable, then, enforce following
# 2*x + 3*y >= 15 ==> w == 1
# w == 1 ==> m + n <= 5
# to test the above, lets fix x = 3 and y = 4
# inequality : 2*x + 3*y >= 15 now will be true,
# and m + n <= 5 should hold true post the solve
x.SetLb(3)
x.SetUb(3)
y.SetLb(4)
y.SetUb(4)
# add w as a binary variable:
w = s.BoolVar("")
# 2*x + 3*y >= 15 ==> w == 1
# a*x - (M + e) * w <= b - e
# a, x represent coefficients and variables
# e (read: epsilon) is some small tolerance value beyond which we will
# regard the constraint as having been broken
# is variables are integers, we can take e = 1
# M (big_M) is the upper bound on 2*x + 3*y - 15
# b is the RHS of the constraint
big_M_1 = 2*x.ub() + 3*y.ub() - 15
s.Add(2*x + 3*y - (big_M_1 + e) * w <= 15 - e)
# now we express : w == 1 ==> m + n <= 5
# a*x - b <= M * (1 - w)
# M (big_M) is the upper bound on : m + n - 5
big_M_2 = m.ub() + n.ub() - 5
s.Add(m + n - 5 <= big_M_2 * (1 - w))
s.Maximize(x + y + m + n)
s.Solve()
s.Objective().Value() # objective function value
print("x == " + str(x.SolutionValue())) # x = 3
print("y == " + str(y.SolutionValue())) # y = 4
print("m == " + str(m.SolutionValue())) # m = 5
print("n == " + str(n.SolutionValue())) # n = 0
print("w == " + str(w.SolutionValue())) # w = 1
as you see since we fixed x, y to be 3 and 4 respectively, 2x + 3y >= 15 is satisfied, which forces m + n <= 5 (m = 5 and n = 0 in optimal solution). This is despite of the fact that we are maximising x + y + m + n
(without the constraint, m, n would take their upper bound values.
答案2
得分: 1
以下是您要翻译的代码部分:
import pulp
m = pulp.LpVariable('m', lowBound=0, upBound=40)
n = pulp.LpVariable('n', lowBound=0, upBound=40)
x = pulp.LpVariable('x', lowBound=2.4)
y = pulp.LpVariable('y', lowBound=3.2) # Increase lower bound to see constraint changes
b = pulp.LpVariable('b', cat=pulp.LpBinary)
prob = pulp.LpProblem(name='conditional_demo', sense=pulp.LpMinimize)
prob.objective = x + y - m - n
# If 2x + 3y < 15, b == 0.
# If 2x + 3y >= 15, b == 1.
# Epsilon must be used for the first expression, otherwise b is unconstrained at 2x + 3y == 15
# p must be a coefficient sufficiently large that it accounts for the highest possible values of x, y
epsilon = 1e-3
p = 3
prob.addConstraint(b >= ((2*x + 3*y)/15 - 1)/p + epsilon)
prob.addConstraint(b <= (2*x + 3*y)/15)
# If b == 0, then m + n is unconstrained
# If b == 1, then m + n <= 5
# M should be sufficiently large that it will always exceed realistic values of m + n - 5
M = 100
prob.addConstraint(m + n <= 5 + (1-b)*M)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('m =', m.value())
print('n =', n.value())
print('x =', x.value())
print('y =', y.value())
print('b =', b.value(), 'because 2x+3y =', 2*x.value() + 3*y.value())
m = 5.0
n = 0.0
x = 2.4
y = 5.2
b = 1.0 because 2x+3y = 20.400000000000002
请注意:由于对m和n的约束是单向的,b
也可以是单向的;也就是说,您可以将其从二进制变量放宽为具有单边整数上限的变量。
英文:
The proper solution is strongly dependent on the possible ranges of x, y, a, b and their integrality. The following is a demonstration only, and you'll need to tune the parameters for whatever it is you're actually doing, in particular the values of M
and p
for the big-M constraints.
import pulp
m = pulp.LpVariable('m', lowBound=0, upBound=40)
n = pulp.LpVariable('n', lowBound=0, upBound=40)
x = pulp.LpVariable('x', lowBound=2.4)
y = pulp.LpVariable('y', lowBound=3.2) # Increase lower bound to see constraint changes
b = pulp.LpVariable('b', cat=pulp.LpBinary)
prob = pulp.LpProblem(name='conditional_demo', sense=pulp.LpMinimize)
prob.objective = x + y - m - n
# If 2x + 3y < 15, b == 0.
# If 2x + 3y >= 15, b == 1.
# Epsilon must be used for the first expression, otherwise b is unconstrained at 2x + 3y == 15
# p must be a coefficient sufficiently large that it accounts for the highest possible values of x,y
epsilon = 1e-3
p = 3
prob.addConstraint(b >= ((2*x + 3*y)/15 - 1)/p + epsilon)
prob.addConstraint(b <= (2*x + 3*y)/15)
# If b == 0, then m + n is unconstrained
# If b == 1, then m + n <= 5
# M should be sufficiently large that it will always exceed realistic values of m + n - 5
M = 100
prob.addConstraint(m + n <= 5 + (1-b)*M)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('m =', m.value())
print('n =', n.value())
print('x =', x.value())
print('y =', y.value())
print('b =', b.value(), 'because 2x+3y =', 2*x.value() + 3*y.value())
m = 5.0
n = 0.0
x = 2.4
y = 5.2
b = 1.0 because 2x+3y = 20.400000000000002
Note: since constraints on m,n are one-sided, b
may also be one-sided; that is, you can loosen it from a binary variable to a singly-bounded integral variable:
import pulp
m = pulp.LpVariable('m', lowBound=0, upBound=40)
n = pulp.LpVariable('n', lowBound=0, upBound=40)
x = pulp.LpVariable('x', lowBound=6)
y = pulp.LpVariable('y', lowBound=6) # Change lower bound to see constraint changes
b = pulp.LpVariable('b', cat=pulp.LpInteger, upBound=1)
prob = pulp.LpProblem(name='conditional_demo', sense=pulp.LpMinimize)
prob.objective = x + y - m - n
# If 2x + 3y < 15, b == 0.
# If 2x + 3y >= 15, b == 1.
# Epsilon must be used for the first expression, otherwise b is unconstrained at 2x + 3y == 15
# p must be a coefficient sufficiently large that it accounts for the highest possible values of x,y
epsilon = 1e-3
p = 3
prob.addConstraint(b >= ((2*x + 3*y)/15 - 1)/p + epsilon)
prob.addConstraint(b <= (2*x + 3*y)/15)
# If b == 0, then m + n is unconstrained
# If b == 1, then m + n <= 5
# M should be sufficiently large that it will always exceed realistic values of m + n - 5
M = 100
prob.addConstraint(m + n <= 5 + (1-b)*M)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('m =', m.value())
print('n =', n.value())
print('x =', x.value())
print('y =', y.value())
print('b =', b.value(), 'because 2x+3y =', 2*x.value() + 3*y.value())
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论