Piecewise Continuous Linear Functions Regarding Insurance Rates

• Access throughyour institution
• View Open Manuscript

Innovative Applications of O.R.

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.

Introduction

Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems and can therefore be modeled as mixed integer nonlinear problems (MINLP). In the context of energy optimization, such nonlinear terms model energy conversion or demand/cost functions. Let us consider, for example, energy optimization in hybrid electric vehicles (HEV). In such vehicles the electrical powertrain system has multiple energy sources that it can gather power from to satisfy the propulsion power requested by the vehicle at each instant. The problem usually consists in finding at each instant the optimal power split between the multiple energy sources to satisfy the power demand of a driver on a predefined road section. The variant of the problem called offline assumes that the power demand profile is known a priori. The objective is to minimize the total fuel consumption of the vehicle performing a predefined mission, taking into account the characteristics and the limitations of each energy source, such as the energy losses happening during any energy transfer. Let (P) denote such problem for a HEV operating with two energy sources: (1) a Fuel Cell (FC) stack able to produce power from $P_{\min }^1$ up to $P_{\max }^1$ at each instant $i\in \{1\dots I\},$ (2) a Storage Element (SE) able to retrieve power up to $P_{\min }^2$ and to produce power up to $P_{\max }^2$ at each instant $i\in \{1\dots I\}$ . The amount of energy stored in the SE is also called State Of Charge (SOC). To avoid a premature aging of SE, its state of charge is only allowed to vary between E _min and E _max, typically 25% and 100% of its energy capacity. Problem (P) can be modeled with Eqs. (1)–(5) where $x_i^1,$ $x_i^2$ and $x_i^3$ are the amount of energy produced by the FC, produced by the SE, and retrieved by the SE at instant $i\in \{1\dots I\}$ . Problem (P) is a (MI)NLP because of nonlinear energy conversion functions f ¹, f ², and f ³ continuous on intervals $[P_{\min }^1,P_{\max }^1],$ $]0,P_{\max }^2],$ and $]0,-P_{\min }^2]$ respectively, and verifying $f^1\left(0\right)=f^2\left(0\right)=f^3\left(0\right)=0,$ often with a discontinuity at $P_{\min }^1$ or 0 that requires the introduction of binary variables to be modeled. The mathematical model can be expressed as follows: $\begin{array}{cc}\hfill \mathrm{\left(}\mathrm{P}\right)\min \sum _{i=1}^I{f}^1\left(x_i^1\right)& //minimizetotalcostonFC\end{array}$ subject to (s.t.) $\begin{array}{ccc}\hfill x_i^1+x_i^2-x_i^3\ge P_i,& \forall i\in \{1\dots I\}& //powerdemandsatisfaction\hfill \end{array}$ $\begin{array}{ccc}\hfill \sum _{i=1}^I(f^2\left(x_i^2\right)-f^3\left(x_i^3\right))\le 0& & //finalSOC\ge initialSOC\hfill \end{array}$ $\begin{array}{ccc}& & E_0-E_{\max }\le \sum _{k=1}^i(f^2\left(x_k^2\right)-f^3\left(x_k^3\right))\le E_0-E_{\min },\hfill \\ & & \forall i\in \{1\dots I\}//SOClimits\hfill \end{array}$ $\begin{array}{ccc}& & x_i^1\in \left\{0\right\}\cup [P_{\min }^1,P_{\max }^1],x_i^2\in [0,P_{\max }^2],x_i^3\in [0,-P_{\min }^2]\hfill \\ & & \forall i\in \{1\dots I\}//domaindefinition.\hfill \end{array}$

General MINLPs are NP-hard or even worse, undecidable (Jeroslow, 1973), but some subclasses such as convex MINLP may be easier to solve although still NP-hard. Convex MINLPs have a convex objective function to minimize, and their constraint functions are all convex and upper bounded. In these instances, when the integrity constraints are relaxed the feasible set is convex, and there exist efficient algorithms to solve the resulting convex NLP. However, linear combinations of convex functions do not necessarily result into convex functions. Therefore, the (MI)NLP modeling an energy optimization problem may not be convex even when all energy conversion functions are convex. As a consequence, only small instances may be tractable using standard MINLP solvers. Several real-world applications have been addressed using piecewise linear approximations of the nonlinear functions of the MINLP to obtain a MILP which is easier to solve (see for example Borghetti, D'Ambrosio, Lodi, Martello, 2008, Boukouvala, Misener, Floudas, 2016, Camponogara, de Castro, Plucenio, 2007, D'Ambrosio, Lodi, Martello, 2010). Such approach presents the main advantage of producing solutions faster than purely MINLP-based approaches if not too many additional binary variables or combinatorial conditions have been introduced in the process, meaning that the number of pieces of the piecewise linear (pwl) functions used should be limited. Geißler, Martin, Morsi, and Schewe (2012) explain that the approach suffers from a few drawbacks because the nature of the nonlinearities inherent to the problem may be lost and the solutions obtained from the MILP may have no meaning for the MINLP. If the solution obtained is not satisfactory in terms of feasibility or optimality, then a new pwl approximation may be performed using a higher number of pieces, to obtain a new MILP to solve. A trade-off between accuracy and tractability is difficult to find a priori. This yields an iterative solution procedure with a number of iterations unknown a priori which translates into high computing times, either because several iterations needed to be performed, or because an unnecessary large number of pieces were introduced upfront, resulting into an unnecessarily large MILP that required a high solution time.

As an alternative we propose a straightforward two-phase solution method designed to cut back on the size of the problem solved during each phase, for a given level of accuracy. The first phase consists in bounding each nonlinear term from above and below using a pair of piecewise linear functions satisfying conditions that will be specified in the core of the paper. Contrary to most publications on piecewise linear approximation which focus on the minimization of the approximation error for a given number of pieces or breakpoints that may or may not be equidistant, we aim at minimizing the number of pieces for a given error bound. The second phase of the solution method consists in solving two MILPs obtained from the replacement of the nonlinear functions with one of the two piecewise linear functions. This paper addresses the first phase of the iterative procedure, assuming that the resulting MILPs can be solved efficiently with a MILP solver. If it is not the case, then a specific solution method may need to be designed for them. An example of such case is presented in Ngueveu, Artigues, and Lopez (2016), which focused on the solution of the resulting MILP without specifying how to obtain the piecewise linear functions.

Section snippets

State of the art

Several publications exists on the application of piecewise linear (pwl) approximation on nonlinear univariate functions to solve MINLP problems, but the issue addressed in the large majority of them is to minimize the approximation error given a predefined number of breakpoints or pieces. To the best of our knowledge, only three papers focused on the specific problem of minimizing the number of breakpoints for a given tolerance or bounded approximation error.

Rosen and Pardalos (1986) were the

Non necessarily continuous pwl δ-approximation of continuous nonlinear functions

Let $f:\mathbb{D}=[X_{-},X_{+}]\to \mathbb{R}$ be a function on the compact interval $\mathbb{D}\subset \mathbb{R}$ . A function $g:\mathbb{D}=[X_{-},X_{+}]\to \mathbb{R}$ is a pwl function with $n_g\in \mathbb{N}$ line-segments if $\exists a\in {\mathbb{R}}^{n_g},b\in {\mathbb{R}}^{n_g},x^{\min }\in {[X_{-},X_{+}]}^{n_g}$ and $\forall i\in [1\dots n_g],\exists x_i^{\max }\in ]x_i^{\min },X_{+}],$ such that the following equations are verified: $\begin{array}{ccc}\hfill g\left(x\right)=a_{i}x+b_i,& & \forall i\in [1\dots n_g],\forall x\in [x_i^{\min },x_i^{\max }]\hfill \end{array}$ $\begin{array}{ccc}\hfill x_i^{\max }=x_{i+1}^{\min },& & \forall i\in [1\dots n_g-1]\hfill \end{array}$ $\begin{array}{c}\hfill x_1^{\min }=X_{-}\end{array}$ $\begin{array}{c}\hfill x_{n_g}^{\max }=X_{+}\end{array}$ Such pwl function is said to be defined by $G={\bigcup }_{i=1}^{n_g}([a_i,b_i],[x_i^{\min },x_i^{\max }]),$ and the two end-points $x_i^{\min }$ and $x_i^{\max }$ of each line-segment i are called breakpoints.

A pwl function g is:

From pwl δ-approximation to pwl δ-bounding

A benefit of computing δ-approximators optimal in terms of number of line-segments is to minimize the number of additional binary variables added to obtain the MILP resulting from the replacement of nonlinear terms with their pwl approximators. A drawback of applying δ-approximation is that the optimal solution of the resulting MILP can be infeasible with respect to the original MINLP. In this case the solution may not be of interest for the practitioners who formulated the original problem. A

Drawbacks and limitations of pwl δ-bounding

When applying PLB+MILP, choosing relevant δ values is a challenging issue. The chosen value should be orders of magnitude smaller than the resulting solution cost to provide an acceptable precision level. After solving the MILP, verifying whether the chosen tolerance value δ was sufficiently small in the view of the resulting solution costs is straightforward. If it was not the case then the value of δ is decreased before a new round of pwl bounding then MILP solution. Such iterative procedure

Using ϵ-relative tolerance

To counter the drawbacks identified in Section 5, we propose to perform the upper and lower bounding of energy conversion expressions using non necessarily continuous pwl functions with a relative ϵ-tolerance.

Definition 6.1

On a compactum $\mathbb{D},$ pwl bounding a function $f:\mathbb{D}\to {\mathbb{R}}^{*}$ with a relative tolerance value $ϵ\in [0,1]$ consists in identifying two pwl functions ( $\overline{f}{}^{ϵ},$ f ^ϵ) that verify: $\begin{array}{cc}\hfill \underline{f}{}^{ϵ}\left(x\right)\le f\left(x\right)\le \overline{f}{}^{ϵ}\left(x\right),& \forall x\in \mathbb{D}\end{array}$ $\begin{array}{cc}\hfill |f\left(x\right)-\underline{f}{}^{ϵ}\left(x\right)|\le ϵ|f\left(x\right)|,& \forall x\in \mathbb{D}\end{array}$ $\begin{array}{cc}\hfill |\overline{f}{}^{ϵ}\left(x\right)-f\left(x\right)|\le ϵ|f\left(x\right)|,& \forall x\in \mathbb{D}\end{array}$

Definition 6.1 generalizes the one of Ngueveu et al. (2016) by

Computational results

Models and algorithms run on an Intel(R) Xeon(R) CPU E3-1271 v3 computer with 32 gigabytes RAM using a single core. PLB heuristic algorithms based on a dichotomic search (Algorithm 3) are coded in MATLAB R2017b 64bits. Their parameter α set to 6 specifies the number of significant decimals. Obviously the computing times would be significantly reduced if all algorithms were implemented in C or C++, but the findings, analysis, and conclusions would not differ. MILPs are solved using ILOG CPLEX

Conclusion

The paper presents a two-phase solution method for combinatorial optimization problems involving nonlinear univariate functions such as energy conversion functions. The first phase consists in bounding the nonlinear univariate functions from above and below with two piecewise linear non necessarily continuous functions with a relative ϵ tolerance. The second phase consists in solving the two mixed integer linear programs obtained when replacing the nonlinear terms with their piecewise linear

Acknowledgments

This research benefited from the support of the FMJH Program PGMO, from the support of EDF-Thales-Orange and from the support of the PEPS program from the Cellule Energie of the CNRS.

The author would also like to thank the two anonymous reviewers for their useful comments that helped improving the quality of the paper.

Cited by (4)

Recommended articles (6)

View full text

© 2018 Elsevier B.V. All rights reserved.

gonzalezhimag1974.blogspot.com

Source: https://www.sciencedirect.com/science/article/abs/pii/S0377221718309469

Share this post