Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization using special ordered sets and mixed-integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm for optimizing a separable discontinuous PLF over a closed convex set. It offers slim and sparse linear programming relaxations, sharpness throughout the search tree, and an increased flexibility in branching decisions. The main feature of our algorithm is the generation of convex underestimators at the root node of the search tree and their quick and efficient updates at each node after branching. Convergence to the global optimum is achieved when the PLFs are lower semicontinuous. A Python implementation of our algorithm is tested on knapsack and network flow problems for both continuous and discontinuous PLFs. Our algorithm is compared with four logarithmic MILP formulations solved by Gurobi’s MILP solver as well as Gurobi’s PLF solver. We also compare our method against mixed-integer nonlinear program formulations solved by Gurobi. The numerical experiments indicate significant performance gains up to two orders of magnitude for medium- to large-sized PLFs. Finally, we also give an upper bound on the additive error from PLF approximations of nonconvex separable optimization. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research of S. Rebennack is supported by the Deutsche Forschungsgemeinschaft [Grant 445857709]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0755 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0755 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Support vector machines (SVMs) are a powerful machine learning paradigm, performing supervised learning for classification and regression analysis. A number of SVM models in the literature have made use of advances in mixed-integer linear programming (MILP) techniques in order to perform this task efficiently. In this work, we present three new models for SVMs that make use of piecewise linear (PWL) functions. This allows effective separation of data points where a simple linear SVM model may not be sufficient. The models we present make use of binary variables to assign data points to SVM segments, and hence fit within a recently presented framework for machine learning MILP models. Alongside presenting an inbuilt feature selection operator, we show that the models can benefit from robust inbuilt outlier detection. Experimental results show when each of the presented models is effective, and we present guidelines on which of the models are preferable in different scenarios.

We propose a new upper bounding procedure for global minimization problems with continuous variables and possibly nonconvex inequality and equality constraints. Upper bounds are crucial for standard termination criteria of spatial branch-and-bound (SBB) algorithms to ensure that they can enclose globally minimal values sufficiently well. However, whereas for most lower bounding procedures from the literature, convergence on smaller boxes is established, this does not hold for several methods to compute upper bounds even though they often perform well in practice. In contrast, our emphasis is on the convergence. We present a new approach to verify the existence of feasible points on boxes, on which upper bounds can then be determined. To this end, we resort to existing convergent feasibility verification approaches for purely equality and box constrained problems. By considering carefully designed modifications of subproblems based on the approximation of active index sets, we enhance such methods to problems with additional inequality constraints. We prove that our new upper bounding procedure finds sufficiently good upper bounds so that termination of SBB algorithms is guaranteed after a finite number of iterations. Our theoretical findings are illustrated by computational results on a large number of standard test problems. These results show that compared with interval Newton methods from the literature, our proposed method is more successful in feasibility verification for both, a full SBB implementation (42 instead of 26 test problems) and exhaustive sequences of boxes around known feasible points (120 instead of 29 test problems). History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0162 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0162 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Clustering and regression are two of the most important problems in data analysis and machine learning. Recently, mixed-integer linear programs (MILPs) have been presented in the literature to solve these problems. By modelling the problems as MILPs, they are able to be solved very quickly by commercial solvers. In particular, MILPs for bivariate clusterwise linear regression (CLR) and (continuous) piecewise linear regression (PWLR) have recently appeared. These MILP models make use of binary variables and logical implications modelled through big-M constraints. In this paper, we present these models in the context of a unifying MILP framework for bivariate clustering and regression problems. We then present two new formulations within this framework, the first for ordered CLR, and the second for clusterwise piecewise linear regression (CPWLR). The CPWLR problem concerns simultaneously clustering discrete data, while modelling each cluster with a continuous PWL function. Extending upon the framework, we discuss how outlier detection can be implemented within the models, and how specific decomposition methods can be used to find speedups in the runtime. Experimental results show when each model is the most effective.

The problem of fitting continuous piecewise linear (PWL) functions to discrete data has applications in pattern recognition and engineering, amongst many other fields. To find an optimal PWL function, the positioning of the breakpoints connecting adjacent linear segments must not be constrained and should be allowed to be placed freely. Although the univariate PWL fitting problem has often been approached from a global optimisation perspective, recently, two mixed-integer linear programming approaches have been presented that solve for optimal PWL functions. In this paper, we compare the two approaches: the first was presented by Rebennack and Krasko [Rebennack S, Krasko V (2020) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. 32(2):507–530] and the second by Kong and Maravelias [Kong L, Maravelias CT (2020) On the derivation of continuous piecewise linear approximating functions. INFORMS J. Comput. 32(3):531–546]. Both formulations are similar in that they use binary variables and logical implications modelled by big-[Formula: see text] constructs to ensure the continuity of the PWL function, yet the former model uses fewer binary variables. We present experimental results comparing the time taken to find optimal PWL functions with differing numbers of breakpoints across 10 data sets for three different objective functions. Although neither of the two formulations is superior on all data sets, the presented computational results suggest that the formulation presented by Rebennack and Krasko is faster. This might be explained by the fact that it contains fewer complicating binary variables and sparser constraints. Summary of Contribution: This paper presents a comparison of the mixed-integer linear programming models presented in two recent studies published in the INFORMS Journal on Computing. Because of the similarity of the formulations of the two models, it is not clear which one is preferable. We present a detailed comparison of the two formulations, including a series of comparative experimental results across 10 data sets that appeared across both papers. We hope that our results will allow readers to take an objective view as to which implementation they should use.

Abstract We discuss stochastic optimization problems under distributional ambiguity. The distributional uncertainty is captured by considering an entire family of distributions. Because we assume the existence of data, we can consider confidence regions for the different estimators of the parameters of the distributions. Based on the definition of an appropriate estimator in the interior of the resulting confidence region, we propose a new data-driven stochastic optimization problem. This new approach applies the idea of a-posteriori Bayesian methods to the confidence region. We are able to prove that the expected value, over all observations and all possible distributions, of the optimal objective function of the proposed stochastic optimization problem is bounded by a constant. This constant is small for a sufficiently large i.i.d. sample size and depends on the chosen confidence level and the size of the confidence region. We demonstrate the utility of the new optimization approach on a Newsvendor and a reliability problem.

Prototyping algorithms in algebraic modeling languages has a long tradition. Despite the convenient prototyping platform that modeling languages offer, they are typically seen as rather inefficient with regard to repeatedly solving mathematical programming problems, a concept on which many algorithms are based. The most prominent examples of such algorithms are decomposition methods, such as the Benders decomposition, column generation, and the Dantzig–Wolfe decomposition. In this work, we discuss the underlying reasons for repeated solve deficiency with regard to speed in detail and provide an insider’s look into the algebraic modeling language GAMS. Further, we present recently added features in GAMS that mitigate some of the efficiency drawbacks inherent to the way modeling languages represent model data and ultimately solve a model. In particular, we demonstrate the grid-enabled gather-update-solve-scatter facility and the GAMS object-oriented application programming interface on a large-scale case study that involves a Benders decomposition–type algorithm for a power-expansion planning problem.

Piecewise linear (PWL) functions are used in a variety of applications. Computing such continuous PWL functions, however, is a challenging task. Software packages and the literature on PWL function fitting are dominated by heuristic methods. This is true for both fitting discrete data points and continuous univariate functions. The only exact methods rely on nonconvex model formulations. Exact methods compute continuous PWL function for a fixed number of breakpoints minimizing some distance function between the original function and the PWL function. An optimal PWL function can only be computed if the breakpoints are allowed to be placed freely and are not fixed to a set of candidate breakpoints. In this paper, we propose the first convex model for optimal continuous univariate PWL function fitting. Dependent on the metrics chosen, the resulting formulations are either mixed-integer linear programming or mixed-integer quadratic programming problems. These models yield optimal continuous PWL functions for a set of discrete data. On the basis of these convex formulations, we further develop an exact algorithm to fit continuous univariate functions. Computational results for benchmark instances from the literature demonstrate the superiority of the proposed convex models compared with state-of-the-art nonconvex models.

Abstract We introduce the two‐stage stochastic minimum s − t cut problem. Based on a classical linear 0‐1 programming model for the deterministic minimum s − t cut problem, we provide a mathematical programming formulation for the proposed stochastic extension. We show that its constraint matrix loses the total unimodularity property, however, preserves it if the considered graph is a tree. This fact turns out to be not surprising as we prove that the considered problem is ‐hard in general, but admits a linear time solution algorithm when the graph is a tree. We exploit the special structure of the problem and propose a tailored Benders decomposition algorithm. We evaluate the computational efficiency of this algorithm by solving the Benders dual subproblems as max‐flow problems. For many tested instances, we outperform a standard Benders decomposition by two orders of magnitude with the Benders decomposition exploiting the max‐flow structure of the subproblems.

Absence seizures are characterized by sudden loss of consciousness and interruption of ongoing motor activities for a brief period of time lasting few to several seconds and up to half a minute. Due to their brevity and subtle clinical manifestations absence seizures are easily missed by inexperienced observers. Accurate evaluation of their high frequency of recurrence can be a challenge even for experienced observers. We present a novel method for detecting and analyzing absence seizures acquired from electroencephalogram (EEG) recordings in patients with absence seizures. Six patients were included in this study; two seizure free, of a total recording time of 26 hours, and four experiencing over 100 seizures within 14.5 hours of total recordings. Our algorithm detected only one false positive finding in the first seizure free patients and 148 of 186 continuous uninterrupted 3Hz spike and wave discharge (SWD) epochs in the rest of the patients. Out of the total 38 missed SWD epochs 28 were ≤ 2.1 sec in duration. The remaining epochs included interrupted 3Hz SWDs. Our proposed algorithm offers an efficient automatic detection scheme that can be used in diagnostic and therapeutic evaluations in patients with absence seizures.