Finding the extrema of continuous piecewise linear functions

Abstract

Geniş uygulama alanları olması nedeniyle parçalı doğrusal fonksiyonların etkin tekniklerlemodellenmesi her zaman dikkat çeken bir konu olmuştur. Bu amaçla çeşitli modellemeteknikleri geliştirilmiştir; tamsayı karışık programlama modelleri, dallara ayırma odaklıyöntemler, özel yapıda parçalı doğrusal fonksiyonlar için lineer programlama modelleribu tekniklere örnek olarak gösterilebilir. Bütün bu çalışmalar faydalı olmakla birlikte, yakompleks formüller olmuş veya kısıtlı bir sınıf parçalı doğrusal fonksiyonları modellemeyeyoğunlaşmıştır.Biz bu çalışmada sürekli parçalı doğrusal fonksiyonların uç değerinin başka kısıtlar ol-madığı hallerde bulunmasını sağlayan yeni bir lineer programlama modeli sunmaktayız.Öncelikle modelimizin sürekli parçalı doğrusal fonksiyonların uç değerini tam bir şekildebulduğunu gösteriyoruz. Modelimizi geliştirirken iki gerçekten faydalanıyoruz. Bunlardanilki simplex algoritmasının en iyi sonucu ararken olanaklı bölgenin uç noktalarında gezdiği,ikincisiyse sürekli parçalı doğrusal bir fonksiyonun uç değerinin her zaman kırılma nok-talarında bulunduğudur. Buradan yola çıkarak, geçerli bölgesinin uç noktaları tanımladığıfonksiyonun kırılma noktalarına tamamen denk gelen bir lineer programlama modeli geliştirdik.Böylelikle simplex algoritmasının parçalı doğrusal fonksiyonun uç değerini tam olarak bul-masını sağladık. Modelimiz ikili değişkenler içermediğinden genel amaçlı bir lineer program-lama çözümleyicisiyle çözülebilmektedir. Ayrıca modelimiz literatürde yer alan modellerdendaha az kısıt ve değişken içermektedir. Sonuç olarak, bütün bu özellikler modelimizin kom-pleksitesini azaltırken çözüme ulaşma süresini de kısaltmaktadır. Modelimizi literatürdekien yaygın modellerle hesaplamalı olarak kıyaslayarak da bulgularımızı desteklemekteyiz.Son olarak, modelimizin ayrılabilir parçalı sürekli doğrusal fonksiyonların uç değerlerininbulunması için kullanılabileceğini de gösteriyoruz.

Development of accurate models and efficient solution algorithms for piecewise linear functions (PWL)attracted a lot of attention due to the wide range of application areas of PWL functions. There havebeen several attempts to develop exact and efficient optimization models. All of these attempts provideuseful insights; however, they are either complex or target a very specific class of PWL functions.In this study, we present a novel linear programming formulation to find the extrema of continuous PWLfunctions when there are no other constraints. We first prove that our formulation finds the extrema of any continuous PWL exactly. While developing this formulation we make use of two facts: First, simplexalgorithm moves along the extreme points of feasible region while searching the optimal solution. Second, extrema of any continuous PWL function lies at its break points. We develop a linear programming formulationwith a special feasible region such that extreme points of this region overlap with break points of corresponding PWL function. This property enables simplex algorithm to find extrema of PWL function exactly. Our formulation is free from binary variables and has less number of variables and constraints than existing formulations in literature. Hence, all these properties decrease the complexity of our formulation and CPU time to find the optimal solution. We support our findings by computationally benchmarking our formulation with most common formulations in literature. Finally, we show that our formulation can also be used to find the extrema of separable piecewise continuous linear functions.