英文:
L1 distance constraint or distance objective
问题
我很新于线性规划和优化问题，正在尝试建立一个简单的线性规划问题。
我想要最小化两个二维点之间的L1距离。其中一个点将被预定义，另一个点应该由求解器确定，通过最小化决策变量上的距离。我已经设置了一个类似这样的简单程序：
from ortools.linear_solver import pywraplp
from ortools.init import pywrapinit
solver = pywraplp.Solver.CreateSolver('GLOP')
# 预定义的点
x_pd = 6
y_pd = 4
# 创建变量 -- 决策变量
x = solver.NumVar(0.0, 12.0, 'xr')
y = solver.NumVar(0.0, 8.0, 'yr')
# 定义约束
solver.Add(x <= 5.0)
solver.Add(x >= 7.0)
solver.Add(y - y_pd <= 0)
solver.Minimize(<目标函数>) # 可能的目标函数
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('解决方案:')
print('目标值 =', solver.Objective().Value())
print('x =', x.solution_value())
print('y =', y.solution_value())
else:
print('问题没有最优解。')
我尝试将 x - x_pd 作为目标函数，但它没有给出我期望的结果。从求解器获得的新点远离了预定义的点。
我希望制定它，使新点接近（或完全等于）预定义的点。
是否有任何我可以参考的材料或帖子？如果我能得到一些关于LP问题的制定和约束编程的材料的指导，那将非常好。
英文:
I am very new to Linear Programming and Optimization problems in general and I am trying to set up a simple LP problem.
I want to minimize the L1 distance between two 2D points. One of them will be predefined and the other point should be determined by the solver by minimizing the distance on the decision variables. I have set up a simple program like this:
rom ortools.linear_solver import pywraplp
from ortools.init import pywrapinit
solver = pywraplp.Solver.CreateSolver('GLOP')
# the predefined point
x_pd = 6
y_pd = 4
# create variables -- decision variables
x = solver.NumVar(0.0, 12.0, 'xr')
y = solver.NumVar(0.0, 8.0, 'yr')
# define constraints
solver.Add(x<=5.0)
solver.Add(x>=7.0)
#solver.Add(x - x_pd <= 0) /*** idk if this is correct ***/
solver.Add(y - y_pd <= 0)
solver.Minimize( <objective> ) /*** the possible objective ***/
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('Solution:')
print('Objective value =', solver.Objective().Value())
print('x =', x.solution_value())
print('y =', y.solution_value())
else:
print('The problem does not have an optimal solution.')
I tried putting x - x_pd as an objective function but it did not gave the result which I expect. The new point I got from the solver far away to the predefined point.
I want to formulate it such that the new point is close to(or exactly ) the predefined point.
Is there any material or thread I can refer to? It will be great if I can get some guidance to refer some materials for LP problem formulation and constraint programming.
答案1
得分: 2
两点之间的L1距离 z=(zx,zy) 和 p=(px,py) 为
|px-zx| + |py-zy|
对于线性规划 (LP)，您需要对此进行线性化处理。一般来说，这很困难并且需要二进制变量，但如果我们最小化这个距离，我们可以进行如下处理：
min dx+dy
-dx <= px-zx <= dx
-dy <= py-zy <= dy
其中 dx 和 dy 是额外的（非负）变量。您可以将每个约束分为两个不同的不等式。
英文:
The L1 distance between two points z=(zx,zy) and p=(px,py) is
|px-zx| + |py-zy|
For an LP, you need to linearize this. In general, this is difficult and requires binary variables, but if we minimize this distance, we can do:
min dx+dy
-dx <= px-zx <= dx
-dy <= py-zy <= dy
where dx,dy are additional (non-negative) variables. You can split each constraint in two different inequalities.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论