# Handling binary variables in sedumi solver

 0 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 K Nayak 1●3 accept rate: 0% fbahr ♦ 4.6k●7●16 In the above model, x(i),x(j) are binary. (22 Aug '13, 03:43) R K Nayak

 2 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. answered 22 Aug '13, 09:31 Erling_MOSEK 616●1●4 accept rate: 3%
 0 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. answered 22 Aug '13, 02:52 jfpuget 2.5k●3●10 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
 0 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$$. answered 22 Aug '13, 17:23 Paul Rubin ♦♦ 14.6k●4●13 accept rate: 19% 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 ♦♦
 0 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. answered 23 Aug '13, 09:57 Imre Polik 1●1 accept rate: 0% Well, if it is mixed-integer SOCP then you can use MOSEK from CVX for instance. (23 Aug '13, 10:05) Erling_MOSEK
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: