I would like to formulate the following constraints as a linear constraint:

\(\lvert x_1 - y_1 \rvert + \lvert x_2 - y_2 \rvert + \lvert x_3 - y_3 \rvert > \lvert x_1 + x_2 + x_3 - y_1 - y_2 - y_3 \rvert\)

Basically I am interested in generating mulitple vectors (variables of my optimization problem) that are undominated. Above constraint is one such way to do so. But, the LP formulation that I tried turned out to be problematic therefore, I hope I can get some inputs here on either,

  1. reformulating the above constraint, or

  2. some other methods to generate undominated vectors.

By \(x\) dominate \(y\), I mean \(x_i >= y_i\) for all \(i\).

asked 18 Mar '13, 18:33

Anon123's gravatar image

accept rate: 0%

edited 19 Mar '13, 05:30

fbahr's gravatar image

fbahr ♦

Let a=x1-y1, b=x2-y2 and c=x3-y3. Your constraint can be then be written as

| a | + | b | + | c | >= | a + b + c |

By the triangle inequality, this constraint is always satisfied. Clearly this doesn't express your original intent.

If, as hplan suggested, you want to have at least one of the x's greater than the corresponding y, then you have a disjunctive constraint that can be represented in a mixed integer programming formulation using binary variables. That constraint is non convex, so it cannot be represented in a linear programming formulation.


answered 19 Mar '13, 12:11

Brian%20Borchers's gravatar image

Brian Borchers
accept rate: 21%

I am sorry I should not have posted this question as I also realized a while after posting that it is non-convex constraint.

(19 Mar '13, 18:46) Anon123

You want at least one element y to be larger than the corresponding element of x?

You could introduce boolean variables \(d_i\) and \(e_i\) and some very large constants \(t_i\)

\[x_i - y_i + d_i t_i > 0\]

\[y_i - x_i + e_i t_i > 0\]

\[d_i + e_i = 1\]

\[\sum d_i > 0\]

At least one \(d_i\) is 1, and thus "deactivates" the constraint \(x_i - y_i > 0\) by adding a very large constant to the left side, making it always feasible. \(e_i\) is constrained to be 0 and "activates" the constraint \(y_i - x_i > 0\) .

If you (can) choose \[t_i = upperbound(x_i) - lowerbound(x_i) = upperbound(y_i) - lowerbound(y_i)\], this should work the same as your constraint.

Probably not the most elegant solution, adding lots of boolean variables.... I honestly hope there is an easier way ;).


answered 19 Mar '13, 11:38

hplan's gravatar image

accept rate: 0%

edited 19 Mar '13, 11:40

What if you do the following? I'm assuming a maximization linear programming problem.

  1. Compute the optimal value of the objective, z*, of the original problem P
  2. State that the objective is equal to z* with some tolerance, creating a new problem P'
  3. Do repeated runs with entirely new objective coefficients, all strictly positive.

By definition step 3 will produce non dominated vectors.

To see why, let's assume that x is one of the optimal solution you find with a given objective, and assume y is a feasible vector of P' that dominates x. Then, given all coefficients are positive, the objective value of y should be larger than that of x, QED

The remaining question is how to select the new objective coefficients. The idea would be to select objective that are as different as possible, see for instance for some discussion of it link text


answered 19 Mar '13, 12:48

jfpuget's gravatar image

accept rate: 8%

edited 19 Mar '13, 14:27

jfpuget: Actually that is a very elegant method to find alternative, non-dominated solutions to P.

However I think the original question states that vectors x and y are parts of the solution to P, not both feasible solutions to P.

(19 Mar '13, 13:32) hplan

So, you're saying I have found a very elegant solution to the wrong problem? ;-)

You may be right, let's see how @Anon123 responds.

(19 Mar '13, 13:39) jfpuget

As @hplan comments, x and y are some n-dimensional vectors which are part of the variables of the optimization that I am considering. I needed a constraint on them, so that they do not dominate each other i.e. x_i >= y_i for some i = 1,..,n and x_i < = y_i for some i = 1,..,n. I thought I could write the constraint as an LP but my logic was seriously flawed so I posted here hoping to find some LP/Convex formulations. I do hope people would have studied putting constraints on variables where variable vectors do not dominate each other. Could you please point me to some references.

(19 Mar '13, 18:51) Anon123
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 18 Mar '13, 18:33

Seen: 1,546 times

Last updated: 19 Mar '13, 18:51

OR-Exchange! Your site for questions, answers, and announcements about operations research.