Optimization techniques for modeling with piecewise-linear functions

作     者：Dobrovoczki, Péter Kis, Tamás 

作者机构：Engineering and Management Intelligence Research Laboratory HUN-REN Institute for Computer Science and Control Kende utca 13-17 Budapest1111 Hungary Department of Operations Research Institute of Mathematics Eötös Loránd University Pázmány Péter sétány 1/C Budapest1117 Hungary 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2025年

核心收录：

主　　题：Integer linear programming 

摘      要：In this paper we aim to construct piecewise-linear (PWL) approximations for functions of multiple variables and to build compact mixed-integer linear programming (MILP) formulations to represent the resulting PWL function. On the one hand, we describe a simple heuristic to iteratively construct a triangulation with a small number of triangles, while decreasing the error of the piecewise-linear approximation. On the other hand, we extend known techniques for modeling PWLs in MILPs more efficiently than state-of-the-art methods permit. The crux of our method is that the MILP model is a result of solving some hard combinatorial optimization problems, for which we present heuristic algorithms. The effectiveness of our techniques is demonstrated by a series of computational experiments including a short-term hydropower scheduling problem. Copyright © 2025, The Authors. All rights reserved.