Is there a way to transform an optimization problem that is linear except for one equality constraint which is multivariate non-separable piecewise-linear?

I found a lot of informations for inequality piecewise-linear constraints, but I've had no luck in finding informations about equality constraints.

asked 09 Sep '14, 11:05

giulatona's gravatar image

giulatona
113
accept rate: 0%

edited 11 Sep '14, 09:57

How are the regions on which your pw-linear function is a particular linear function defined? Does \(f(x)=a'x+b\) when \(x\) lies in a (known) hyperrectangle, a polytope with known vertices, a polytope given by inequalities, or something else?

(11 Sep '14, 17:26) Paul Rubin ♦♦

My function only has two regions and these are defined through a linear inequality

(12 Sep '14, 04:37) giulatona

While in the case of linear constraints, strict equality requirements don't affect the convexity properties of constraints in question (i. e., piecewise-linear equality constraints can still be transformed using the usual techniques) [edited, see @Matthew Saltzman's comment below].

For instance (a simple price function w/ quantity discount),

\[ \begin{array}{l} \min & y\\ \text{s.t.} & y = \begin{cases} x & ,~ 0 \le x \le 10 \\ 10 + .99 * ( x - 10 ) & ,~ 10 < x \\ \end{cases} \\ & x \ge \ldots \\ & x \ge 0 \\ \end{array} \]

can be (equivalently) formulated as

\[ \begin{array}{l} \min & y\\ \text{s.t.} & y = 0 * z_1 + 10 * z_2 + ( 10 + .99 * ( M - 10 ) ) * z_3 \\ & x = 0 * z_1 + 10 * z_2 + M * z_3 \\ & 1 = z_1 + z_2 + z_3 \\ & x \ge \ldots \\ & 0 \le x \le M \\ & z ~~\text{SOS2 vars} \end{array} \]

In the rather rare case that your modeling language/solver doesn't support SOS2 variables, binary aux. variables have to be introduced; cf.

link

answered 09 Sep '14, 14:31

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 11 Sep '14, 12:15

Thank you for your response. I would also like to know if there are situations that allow simple reformulation into linear programming and avoid SOS2 or binary variables. For example, if it was a convex PWL function with a less than constraint I know I don't need binary variables. Are there any similar cases for equality constraints?

(11 Sep '14, 06:00) giulatona
2

Piecewise linear equality constraints are nonconvex (unless they reduce to simple linear constraints) even if the PWL function itself is convex, so you won't get away without some sort of nonconvex representation.

(11 Sep '14, 10:11) Matthew Salt... ♦

Thank you, is it possible to use SOS2 representations with multivariate functions? From what I've found so far it seems like it is not possible

(11 Sep '14, 11:12) giulatona
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

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

Tags:

×231
×3

Asked: 09 Sep '14, 11:05

Seen: 1,558 times

Last updated: 12 Sep '14, 04:37

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