I need to linearize z(i,j)=abs(xi-xj) for which I write the following code:

for i=1:n
    for j=1:n
        if(i<=j)
            z(i,j)>=x(i)-x(j);
            z(i,j)<=x(i)-x(j)+2*(y(i,j));
            z(i,j)>=x(j)-x(i);
            z(i,j)<=x(j)-x(i)+1*(1-y(i,j));
            y(i,j)>=0; y(i,j)<=1;
        end
    end
end

where y(i,j) are binary.

This code is wrong as y(i,j) are continuous here.

I am solving in CVX sedumi and sedumi does not accomodate integer variables.

How can I handle the linearization?

Thanking you.

asked 22 Aug '13, 00:17

R%20K%20Nayak's gravatar image

R K Nayak
13
accept rate: 0%

edited 24 Aug '13, 08:30

fbahr's gravatar image

fbahr ♦
4.6k716

In the above model, x(i),x(j) are binary.

(22 Aug '13, 03:43) R K Nayak

Just for clarity then SeDuMi solves linear conic optimization problems. That means you must have something like

min c'x st. A x = b x \in K

where K is a convex cone. Only some special but important convex cones are allowed.

Therefore, SeDuMi cannot deal with integer constrained variables at all. Moreover, it cannot deal with quadratic functions such as x^2 = x because that is a nonconvex set.

If your problem is nonconvex e.g. contain integer variables it might be possible to formulate a convex relaxation that can be solved with SeDuMi.

link

answered 22 Aug '13, 09:31

Erling_MOSEK's gravatar image

Erling_MOSEK
61614
accept rate: 3%

I'd try z(i,j)^2 = (xi-xj)^2, z(i,j) >= 0

Depending on the rest of your model you may get a semi definite positive problem.

link

answered 22 Aug '13, 02:52

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Thanks for the response. I am more intersted in linearization of abs(x(i)-x(j)) where x(i),x(j) are binary. In fact I am intersted in max(x(i),x(j)),where i,j=1,2...n. I have converted max interms of absolute value function. Could you write your model in SDP form?

(22 Aug '13, 04:31) R K Nayak

I proposed a quadratic form because that's what sedumi handles (from their online documentation)

If you want to use a mixed integer model then you should use a solver that handles such models, for instance CPLEX.

(22 Aug '13, 04:36) jfpuget

Thanks again. But I could not follow your model. Means how to solve in cvx_Sedumi unless the above QP is not converted to SDP. Are you saying to convert your model to SDP first and then solve by CVX_Sedumi?

(22 Aug '13, 04:49) R K Nayak

sorry, I wanted to say that depending on the rest of the model the quadratic objective function can be semi definite positive.

sedumi handles linear and quadratic constraints, which is what I have used.

You can express that a variable x is binary with the constraint x = x^2

(22 Aug '13, 05:02) jfpuget

I'm confused about how \(x_i\) can be binary if the solver cannot handle integer variables. At any rate, if they really are binary then \(\left|x_i - x_j\right| = x_i + x_j - 2 x_i x_j\). To linearize \(y_{ij} = x_i x_j\), use \(y_{ij} \le x_i\), \(y_{ij} \le x_j\), \(y_{ij} \ge x_i + x_j - 1\), \(y_{ij} \ge 0\).

link

answered 22 Aug '13, 17:23

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 23 Aug '13, 10:38

Thanks for pointing me about x_i as binary. In fact x_i is binary but I am relaxing it by taking as continuous in [0,1] and I am not declaring in my code x as binary variable. But in the above model of me I have to declare y(i,j) as binary so that the linarization of z(i,j)=|x_i-x_j| is possible.

If x_i is continous, whether your model works?

(22 Aug '13, 22:59) R K Nayak

No, my approach does not work for continuous x.

(23 Aug '13, 10:39) Paul Rubin ♦♦

I suggest you formulate your problem in Yalmip as it has an integer conic solver built in and it is hooked up to sedumi as a backend solver.

link

answered 23 Aug '13, 09:57

Imre%20Polik's gravatar image

Imre Polik
11
accept rate: 0%

edited 23 Aug '13, 09:57

Well, if it is mixed-integer SOCP then you can use MOSEK from CVX for instance.

(23 Aug '13, 10:05) Erling_MOSEK
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×65
×6
×4
×2

Asked: 22 Aug '13, 00:17

Seen: 1,702 times

Last updated: 24 Aug '13, 08:30

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