1
$\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.

$\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$ Commented Feb 13, 2023 at 15:59
  • 2
    $\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$ Commented Feb 13, 2023 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$ Commented Feb 14, 2023 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$ Commented Feb 14, 2023 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$ Commented Feb 16, 2023 at 17:52

1 Answer 1

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.

$\endgroup$
1
  • $\begingroup$ Multiplying by $\delta$ makes things cubic. This is not how I would formulate piecewise functions. $\endgroup$ Commented Feb 14, 2023 at 2:49

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.