4
$\begingroup$

Note: Initially posted on MathOverflow.

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^- x $
  • $x' \leq c^+ 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 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$
1
  • 1
    $\begingroup$ These things are difficult to predict. Best advice is: try it out. In general: if I am developing a large model and I did not try out many variants and formulations, I did not do my job. $\endgroup$
    – Erwin Kalvelagen
    Commented Mar 12, 2021 at 17:13

1 Answer 1

Reset to default
3
$\begingroup$

within CPLEX you can use piecewise linear function in the objective with all APIs.

Let me show how to do that in OPL. Let me use the example from Making Optimization Simple

Piecewise linear function

/*
let s now deal with a new information : for a given bus size if we take more than 4 then we get a 20% discount.
This moves our function cost from linear to piecewise linear. Let's have a look at how to deal with this in OPL.
 
We would then write:
*/



int nbKids=300;
float costBus40=500;
float costBus30=400;

// If we take more than 4 buses for a given size, 20% cheaper for additional buses
 
dvar int+ nbBus40;
dvar int+ nbBus30;

pwlFunction pricePerQuantity=piecewise{1->4;0.8};

assert forall(k in 1..4 ) pricePerQuantity(k)==k;
assert forall(k in 5..10) as:abs(pricePerQuantity(k)-4-(k-4)*0.8)<=0.00001;
 
minimize
 costBus40*pricePerQuantity(nbBus40)  +pricePerQuantity(nbBus30)*costBus30;
 
subject to
{
 40*nbBus40+nbBus30*30>=nbKids;
}

NB: I am an IBMer

Improve this answer
$\endgroup$
3
  • $\begingroup$ In your example, the optimization domain is still convex, isn't it ? This is the equivalent of the case where $c^- \geq c^+$ in my original question, which can be solved with traditional linear programming. Would your example work as well and give an optimal solution in a reasonable amount of time if taking more buses had an extra fare associated to it ? $\endgroup$
    – lovasoa
    Commented Mar 11, 2021 at 10:12
  • 1
    $\begingroup$ Hi, if not convex it will work. Could be slower sometimes. $\endgroup$
    – Alex Fleischer
    Commented Mar 11, 2021 at 10:55
  • $\begingroup$ Do you know what cplex uses to be able to solve this class of problems ? If there is a large number of places where the optimization domain is not convex, how can it find an optimal solution in a reasonable amount of time ? $\endgroup$
    – lovasoa
    Commented Mar 12, 2021 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.