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.


  • x - vector of decision variables
  • c_i(x) - cost function for each x

So the problem needs to be minimized: min z(x) = sum(c(x))

L <= x <= U

where c(x) =
n * |x| if x < 0
m * x if x >= 0

n, m are constant.

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?

Thank you in advance.

asked 13 Jul '16, 05:00

Thomas's gravatar image

accept rate: 0%

edited 13 Jul '16, 05:20

Under the following conditions, you can model it without any binary variables:

  • \(m\ge 0\) and \(n\ge 0\);
  • \(c(x)\) does not appear in any constraints (other than those defining it).

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.

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):

\(c(x) \ge m * x,\) \(c(x) \ge -n * x.\)

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)\).


answered 13 Jul '16, 15:34

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Sorry for the misunderstanding notation. Your approach worked fine for my problem. Thank you very much!

(15 Jul '16, 04:37) Thomas
Your answer
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: 13 Jul '16, 05:00

Seen: 739 times

Last updated: 15 Jul '16, 04:37

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