Hi, 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,
By \(x\) dominate \(y\), I mean \(x_i >= y_i\) for all \(i\). 
Let a=x1y1, b=x2y2 and c=x3y3. 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 Borchers I am sorry I should not have posted this question as I also realized a while after posting that it is nonconvex 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 
What if you do the following? I'm assuming a maximization linear programming problem.
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 jfpuget: Actually that is a very elegant method to find alternative, nondominated 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 ndimensional 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
