2
$\begingroup$

I have inherited a reasonably simple ortools-based optimizer (Python) with linear relationships that I need to non-linear-ize, and I have no idea how to do that.

The relevant part of my problem looks like this:

solver = pywraplp.Solver("B", pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
...
# charging a battery
## cap_prev: capacity before the current timeslot
## cap: ditto afterwards
## b_chg: charging power
## all are NumVar(0,some_hardware_limit)

solver.Add(cap_prev + 0.9 * b_chg - b_dis == cap)

The problem is that I need to replace the 0.9 with something that depends on the value of b_chg. The Naïve solution looks like this:

solver.Add(cap_prev + b_chg_eff - b_dis == cap)

solver.Add(b_chg_eff == b_chg * (0.1+b_chg*0.8)).OnlyEnforceIf(b_chg<100)
solver.Add(b_chg_eff == b_chg * (0.9).OnlyEnforceIf(100<=b_chg<200)
solver.Add(b_chg_eff == b_chg * (0.9-(b_chg-200)*0.01).OnlyEnforceIf(200<=b_chg)

except that this is no longer linear, which kindof points to the assumption that I need a different solver.

Unfortunately I'm just starting off with OR in general, and ORtools in particular, and don't even know where to look next …

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ This is piecewise quadratic. And in addition, non-convex (all quadratic equality constraints are non-convex). I would look into adding more segments and using a piecewise linear approximation. Standard formulations are available for piecewise linear functions. $\endgroup$
    – Erwin Kalvelagen
    Feb 13 at 15:59
  • 1
    $\begingroup$ You can use CP-SAT (your example borrowed some of its API). You will need to scale all floating points to integer, use integer variables, and read github.com/google/or-tools/blob/stable/ortools/sat/docs/… for the OnlyEnforceIf part. You will also need to use AddMultiplicationEquality() and intermediate variables. $\endgroup$
    – Laurent Perron
    Feb 13 at 16:22
  • $\begingroup$ Well, sure, I can auto-generate something piecewise-linear from my piecewise-quadratic formula … but won't that result in a suboptimal solution? seems to me that a stepwise linearization would add a heap of local maxima (of unknown magnitude) to the problem. $\endgroup$
    – Matthias Urlichs
    Feb 14 at 18:07
  • 1
    $\begingroup$ What is "stepwise linearization"? You mean a step function? No, piecewise linearization is different. Error bounds on the approximation are known a priori. "local maxima"? How so? MIP solvers are global solvers. I suggest discussing with your teacher, as there is some confusion here. $\endgroup$
    – Erwin Kalvelagen
    Feb 14 at 21:02
  • $\begingroup$ What teacher?? Yes I can approximate with arbitrary error bounds, nice, do I write my own code to assemble the approximation or are there solvers that include appropriate support code? Also, well, nice to know that MIP solvers in general do global optimization, but I was kindof hoping there's some resource out there that explains using concrete code, not abstract math, how to go from what I have to where I need to go with this. I can't possibly be the only person who builds a linear model and then gets confronted with nonlinear requirements. $\endgroup$
    – Matthias Urlichs
    Feb 16 at 17:52

1 Answer 1

Reset to default
0
$\begingroup$

If you are looking to linearize the 3 conditional relations/constraints below is what you may do
$ 200\delta_3+ 100\delta_2 \le$ b_chng $\le (200+e)\delta_2 +(100+e)\delta_1 $
$ \sum_{i=1}^3\delta_i = 1$ where $\delta$ are binary and e is a very small number (like $1e-3$).

Then
b_chng_eff= 1st Constr1$\delta_1$+2nd_Constr$\delta_2$+3rd_Constr$\delta_3$

As for the 2nd degree quads for 2 of the above relations, most solvers will be able to accept these constraints. Else you may choose piecewise linearization as suggested here, scroll down to piecewise linear constraints.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Multiplying by $\delta$ makes things cubic. This is not how I would formulate piecewise functions. $\endgroup$
    – Erwin Kalvelagen
    Feb 14 at 2:49

Your Answer

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

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