Hi,

I want to put the following constraint(s) in my linear program:

||xi-xj|| <= some constant,
for all pairs i and j, 1<=i<=N, 1<=j<=N.

Here, x1,x2,... are all vectors, and the norm is L1 norm.

Since N is not a small number (around 100 for now, but can be 1000 in
future), there are many possible pairs (100 pick 2).

Is it a "reasonable" thing to put these things as constraints?

Is there perhaps another way to formulate the constraints into another
(closely) equivalent form, so that the linear program looks less
daunting?

bahoo wrote:
Hi,

I want to put the following constraint(s) in my linear program:

||xi-xj|| <= some constant,
for all pairs i and j, 1<=i<=N, 1<=j<=N.

Here, x1,x2,... are all vectors, and the norm is L1 norm.How do you intend to write these constraints? You can't use the
absolute value function (it's not linear). A common trick is to write

x_ik - x_jk = u_ijk - v_ijk (new variables u, v nonnegative)

and then constrain sum_i,j,k (u_ijk + v_ijk) <= some constant.

That means that you are adding K+1 constraints and 2*K variables (about
3*K if you count artificial and slack variables) for each pair of
vectors, where K is the dimension of the vectors.



Since N is not a small number (around 100 for now, but can be 1000 in
future), there are many possible pairs (100 pick 2).

Is it a "reasonable" thing to put these things as constraints?Depends -- how many CPUs do you have in your supercomputer? :-)

Actually, when N is around 100, it's probably not too bad (assuming you
have a commercial solver, not home-brew code). For N around 1,000, I'm
not sure -- with good commercial code, lots of memory and a fast
processor, I'm pretty sure it's possible, but I'm not sure.

One possibility is to omit the norm constraints to start with. Each
time the LP solver comes up with what it thinks is an optimal solution,
check all the norms, and if any are violated, add the necessary
constraints and variables and restart the solution process. This is not
as duplicative as it sounds, since current solvers can usually be
hot-started from the previous solution and then do a comparatively small
number of dual simplex pivots to regain feasibility. The hope is that
the bulk of the norm constraints will never be needed.

Another possibility is to switch to the zero-norm (a.k.a infinity-norm
a.k.a. sup-norm). The corresponding constraints for vector pair i,j become

-some constant <= x_ik - x_jk <= some constant for k = 1,...,K

which adds more constraints but fewer variables.



Is there perhaps another way to formulate the constraints into another
(closely) equivalent form, so that the linear program looks less
daunting?I don't know how close an approximation this is, but if you have some
idea where the "center of mass" of the vectors is likely to end up, you
could require them all to be within "some constant"/2 of that (static)
point, which would keep them within "some constant" of each other. If
you're willing to accept a compromise like that but don't know the
center of mass, you could make the center of mass another variable, add
a constraint (actually, K constraints) that it equals the sum of the
other vectors divided by N, and then add norm constraints keeping each
vector within "some constant"/2 of the new vector. That cuts you from
o(N^2) pairings to o(N) pairings.

/Paul

On Jan 14, 5:20 pm, "Paul A. Rubin" <r...@msu.edu> wrote:
bahoo wrote:
Hi,

I want to put the following constraint(s) in my linear program:

||xi-xj|| <= some constant,
for all pairs i and j, 1<=i<=N, 1<=j<=N.

Here, x1,x2,... are all vectors, and the norm is L1 norm.How do you intend to write these constraints? You can't use the
absolute value function (it's not linear). A common trick is to write

x_ik - x_jk = u_ijk - v_ijk (new variables u, v nonnegative)

and then constrain sum_i,j,k (u_ijk + v_ijk) <= some constant.

That means that you are adding K+1 constraints and 2*K variables (about
3*K if you count artificial and slack variables) for each pair of
vectors, where K is the dimension of the vectors.



Since N is not a small number (around 100 for now, but can be 1000 in
future), there are many possible pairs (100 pick 2).

Is it a "reasonable" thing to put these things as constraints?Depends -- how many CPUs do you have in your supercomputer? :-)

Actually, when N is around 100, it's probably not too bad (assuming you
have a commercial solver, not home-brew code). For N around 1,000, I'm
not sure -- with good commercial code, lots of memory and a fast
processor, I'm pretty sure it's possible, but I'm not sure.

One possibility is to omit the norm constraints to start with. Each
time the LP solver comes up with what it thinks is an optimal solution,
check all the norms, and if any are violated, add the necessary
constraints and variables and restart the solution process. This is not
as duplicative as it sounds, since current solvers can usually be
hot-started from the previous solution and then do a comparatively small
number of dual simplex pivots to regain feasibility. The hope is that
the bulk of the norm constraints will never be needed.

Another possibility is to switch to the zero-norm (a.k.a infinity-norm
a.k.a. sup-norm). The corresponding constraints for vector pair i,j become

-some constant <= x_ik - x_jk <= some constant for k = 1,...,K

which adds more constraints but fewer variables.



Is there perhaps another way to formulate the constraints into another
(closely) equivalent form, so that the linear program looks less
daunting?I don't know how close an approximation this is, but if you have some
idea where the "center of mass" of the vectors is likely to end up, you
could require them all to be within "some constant"/2 of that (static)
point, which would keep them within "some constant" of each other. If
you're willing to accept a compromise like that but don't know the
center of mass, you could make the center of mass another variable, add
a constraint (actually, K constraints) that it equals the sum of the
other vectors divided by N, and then add norm constraints keeping each
vector within "some constant"/2 of the new vector. That cuts you from
o(N^2) pairings to o(N) pairings.

/Paul

Paul, thanks, your suggestions really helped a lot.

Following your suggestion, I have a more fundamental question about
linear programming. Suppose I take the "center of mass" approach above,
which says, define a new variable as the center of mass, and let D =
sum of the distances from all point to the center of mass.
Can I say that these two formulations below are equivalent?
Constraint-approach: (1) Put a constraint D <= some constant c1 in the
linear program.
Objective-approach: (2) Add a new term "some constant c2 times D" to
the objective function to be minimized.

So, one can go with either one, depending on which constant (c1 or c2)
is easier to design or its availability.
Thanks!
bahoo

Following your suggestion, I have a more fundamental question about
linear programming. Suppose I take the "center of mass" approach above,
which says, define a new variable as the center of mass, and let D =
sum of the distances from all point to the center of mass.

Can I say that these two formulations below are equivalent?
Constraint-approach: (1) Put a constraint D <= some constant c1 in the
linear program.
Objective-approach: (2) Add a new term "some constant c2 times D" to
the objective function to be minimized.

So, one can go with either one, depending on which constant (c1 or c2)
is easier to design or its availability.