Answers to: Linear Optimization with piecewise functionhttp://www.or-exchange.com/questions/13997/linear-optimization-with-piecewise-function<p>Hi, i'm a bit in struggle with the optimization below and I'd be grateful for any help or hint. The problem deals with the "relaxation" of the non-negativity constraint, i.e. my decision variables x can be negative. The cost function c_i(x) shall stay positive. Assume that x is bounded in between a lower and upper bound.</p>
<p>Let</p>
<ul>
<li>x - vector of decision variables</li>
<li>c_i(x) - cost function for each x</li>
</ul>
<p>So the problem needs to be minimized:
min z(x) = sum(c(x)) <br></p>
<p>s.t.<br> L <= x <= U</p>
<p>where c(x) = <br>
n * |x| if x < 0 <br>
m * x if x >= 0</p>
<p>n, m are constant.</p>
<p>Do you know any to convert this function (e.g. by using binary variables?) such that I am able to solve this problem by a linear solver?</p>
<p>Thank you in advance.</p>enWed, 13 Jul 2016 15:34:29 -0400Answer by Paul Rubinhttp://www.or-exchange.com/questions/13997/linear-optimization-with-piecewise-function/13999<p>Under the following conditions, you can model it without any binary variables:</p>
<ul>
<li>\(m\ge 0\) and \(n\ge 0\);</li>
<li>\(c(x)\) does not appear in any constraints (other than those defining it).</li>
</ul>
<p>The reason for the second condition is that for this approach to work, there cannot be any "pressure" for \(c(x)\) to be larger than the conditional definition you gave.</p>
<p>Under those conditions (and the objective function you named), you just need the following two constraints (elementwise if \(x\) is a vector, which seems likely but is a bit unclear given your notation):</p>
<p>\(c(x) \ge m * x,\)
\(c(x) \ge -n * x.\)</p>
<p>For any non-zero \(x\), the right-side of one inequality will be negative, and the right-side of the other will be the correct value of \(c(x)\).</p>Paul RubinWed, 13 Jul 2016 15:34:29 -0400http://www.or-exchange.com/questions/13997/linear-optimization-with-piecewise-function/13999