1
$\begingroup$

Crossposted on Operations Research SE.

I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- x, & x \leq 0 \\ c^+ x, & x > 0 \\ \end{cases} $$

as depicted below

objective function plot

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

  • $x' \leq c^- \times x $
  • $x' \leq c^+ \times x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

I have heard about SOS constraints. Are they the canonical way to solve this kind of problem ? If my problem contains many such piecewise linear functions, is it reasonable to expect a free solver from being able to solve such a problem with thousands of SOS1 constraints ?

Example

$$\begin{array}{ll} \text{maximize} & a \max(x,0) + b \min(x,0) + c \max(y,0) + d \min(y,0)\\ \text{subject to} & x,y \in [−1,1]\end{array}$$

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ I would write $c_+$ instead, since $c^+$ is a bit too close to $c$ transposed. $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 9, 2021 at 20:31
  • 1
    $\begingroup$ When $c^- > c^+$, you can solve the problem because it is convex. When $c^- < c^+$, the problem is non-convex. $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 9, 2021 at 20:38
  • $\begingroup$ Yes, exactly, the feasible region is not convex. So the question is: what is the canonical way of solving such problems ? $\endgroup$
    – lovasoa
    Commented Mar 9, 2021 at 22:41
  • $\begingroup$ Yes, the objective function is piecewise linear and all the variables are bounded, so the objective has a finite maximum. $\endgroup$
    – lovasoa
    Commented Mar 10, 2021 at 8:27
  • $\begingroup$ Every $\min$ / $\max$ introduces a Boolean variable. Thus, in your example, you have $2^4 = 16$ "branches". The maximum of each of these branches can be found via LP. Lastly, find the $\max$ of the $16$ maxima. There are smarter ways of doing it. If you can determine whether the objective to be maximized is concave, it is much easier. $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 10, 2021 at 19:09

0

Reset to default

You must log in to answer this question.