Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods.

Abstract : Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems. In the context of energy optimization for example, energy sources can have very different characteristics in terms of power range and energy demand/cost function, also known as efficiency function or energy conversion function. Introducing these energy sources characteristics in combinatorial optimization problems, such as energy resource allocation problems or energy-consuming activity scheduling problems may result into mixed integer nonlinear problems neither convex nor concave. Approximations via piecewise linear functions have been proposed in the literature. Non-convex optimization models and heuristics exist to compute optimal breakpoint positions under a bounded absolute error-tolerance. We present an alternative solution method based on the upper and lower bounding of nonlinear terms using non necessarily continuous piecewise linear functions with a relative epsilon-tolerance. Conditions under which such approach yields a pair of mixed integer linear programs with a performance guarantee are analyzed. Models and algorithms to compute the non necessarily continuous piecewise linear functions with absolute and relative tolerances are also presented. Computational evaluations performed on energy optimization problems for hybrid electric vehicles show the efficiency of the method with regards to the state of the art.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01444317
Contributor : Sandra Ulrich Ngueveu <>
Submitted on : Wednesday, May 30, 2018 - 6:30:45 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Friday, August 31, 2018 - 7:01:37 PM

File

PWLB_v3_SUN.pdf
Files produced by the author(s)

Identifiers

Citation

Sandra Ulrich Ngueveu. Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods.. European Journal of Operational Research, Elsevier, 2018, ⟨10.1016/j.ejor.2018.11.021⟩. ⟨hal-01444317v3⟩

Share

Metrics

Record views

694

Files downloads

553