StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you are minimizing an increasing function of <code>|x|</code> (or maximizing a decreasing function, of course), you can always have the aboslute value of any quantity <code>x</code> in a lp as a variable <code>absx</code> such as:</p> <pre><code>absx >= x absx >= -x </code></pre> <p>It works because the value <code>absx</code> will 'tend' to its lower bound, so it will either reach <code>x</code> or <code>-x</code>.</p> <p>On the other hand, if you are minimizing a decreasing function of <code>|x|</code>, your problem is not convex and cannot be modelled as a <code>lp</code>.</p> <p>For all those kind of questions, it would be much better to add a simplified version of your problem <em>with the objective</em>, as this it often usefull for all those modelling techniques.</p> <p><strong>Edit</strong></p> <p>What I meant is that there is <em>no</em> general solution to this kind of problem: you cannot in general represent an absolute value in a linear problem, although in practical cases it is often possible.</p> <p>For example, consider the problem:</p> <pre><code>max y y <= | x | -1 <= x <= 2 0 <= y </code></pre> <p>it is bounded and has an obvious solution (2, 2), but it <em>cannot</em> be modelled as a lp because the domain is not convex (it looks like the shape under a 'M' if you draw it).</p> <p>Without your model, it is not possible to answer the question I'm afraid.</p> <p><strong>Edit 2</strong></p> <p>I am sorry, I did not read the question correctly. If you can use binary variables <em>and</em> if all your distances are bounded by some constant <code>M</code>, you can do something.</p> <p>We use:</p> <ul> <li>a continuous variable <code>ax</code> to represent the absolute value of the quantity <code>x</code></li> <li>a binary variable <code>sx</code> to represent the sign of <code>x</code> (<code>sx = 1</code> if <code>x >= 0</code>)</li> </ul> <p>Those constraints are always verified if <code>x < 0</code>, and enforce <code>ax = x</code> otherwise:</p> <pre><code> ax <= x + M * (1 - sx) ax >= x - M * (1 - sx) </code></pre> <p>Those constraints are always verified if <code>x >= 0</code>, and enforce <code>ax = -x</code> otherwise:</p> <pre><code> ax <= -x + M * sx ax >= -x - M * sx </code></pre> <p>This is a variation of the "big M" method that is often used to linearize quadratic terms. Of course you need to have an upper bound of all the possible values of <code>x</code> (which, in your case, will be the value of your distance: this will typically be the case if your points are in some bounded area)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload