L1 distance constraint or distance objective

Question

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.

Answer 1

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.