I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either with Gurobi or CPLEX. I'm having a really hard time modeling the last, but crucial, part of the model.

I have continuous variables that represent the positions of a known number of points in the \(\mathbb{R}^2\) plane : they vary in a given \(B=[x_\text{min},x_\text{max}]\times [y_\text{min},y_\text{max}]\subset \mathbb{R}^2\) box. For each couple of points \((p,p')\in B^2\), I'm interested in having a binary variable \(u_{pp'}\) that would be equal to 1 if and only if \(||p' - p|| \leq \delta\) where \(\delta\) is a separation threshold defined as an input data.

Note that for Gurobi and CPLEX, the quadratic constraints must have the following form : \(X^TQX + q^TX \leq b\) where Q is a semi-definite positive matrix.

Let \(\Delta = || (x_\text{max},y_\text{max}) - (x_\text{min},y_\text{min})||\). Using \(\delta^2\), \(\Delta^2\) and the canonical scalar product of \(\mathbb{R}^2\), I think we can have a valid constraint that forces the binary variables to be equal to 0 for the couples of points that are seperated by a distance greater or equal than \(\delta\), it would look like this :

\(1-u_{pp'}\geq \dfrac{\text{distance_between_p_and_p'}^2-\delta^2}{\Delta^2}\)

where \(\text{distance_between_p_and_p'}^2\) is a term of the form "\(X^TQX\)". In that case, the inequality is is the right sense, Q is semi-definite positive : it looks OK to me.

I am now looking for a way to have to complementary implication : the binary variable equal to 1 when two points are too close according to the \(\delta\) threshold. Do you think that is possible ? Do you have any advice ?

Thanks a lot !

asked 12 Dec '14, 08:59

Sycropane's gravatar image

accept rate: 0%

edited 12 Dec '14, 09:48

Be the first one to answer this question!
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: 12 Dec '14, 08:59

Seen: 914 times

Last updated: 12 Dec '14, 09:48

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