Explore the vast range of titles available.

In this paper, an open-source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The POA is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended supporting hyperplane (ESH) and extended cutting plane (ECP) algorithms. The dual strategy can be tightly integrated with the mixed-integer programming (MIP) subsolver in a so-called single-tree manner, i.e., only a single MIP optimization problem is solved, where the polyhedral linearizations are added as lazy constraints through callbacks in the MIP solver. This enables the MIP solver to reuse the branching tree in each iteration, in contrast to most other POA-based methods. SHOT is available as a COIN-OR open-source project, and it utilizes a flexible task-based structure making it easy to extend and modify. It is currently available in GAMS, and can be utilized in AMPL, Pyomo and JuMP as well through its ASL interface. The main functionality and solution strategies implemented in SHOT are described in this paper, and their impact on the performance are illustrated through numerical benchmarks on 406 convex MINLP problems from the MINLPLib problem library. Many of the features introduced in SHOT can be utilized in other POA-based solvers as well. To show the overall effectiveness of SHOT, it is also compared to other state-of-the-art solvers on the same benchmark set.

In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.

A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, E , and a split disjunction, ( l - x j ) ( x j - u ) ≤ 0 with l < u , equals the intersection of E with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form K ∩ Q and K ∩ Q ∩ H , where K is a SOCr cone, Q is a nonconvex cone defined by a single homogeneous quadratic, and H is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations K ∩ S and K ∩ S ∩ H , where S is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.

Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves.

We consider the problem of designing lightweight load-bearing frame structures with additive manufacturability constraints. Specifically, we focus on mathematical programming approaches to finding exact globally optimal solutions, given a pre-specified discrete ground structure and continuous design element dimensions. We take advantage of stiffness matrix decomposition techniques and expand on some of the existing modeling approaches, including exact mixed-integer nonlinear programming and its mixed-integer linear programming restrictions. We propose a (non-convex) quadratic formulation using semi-continuous variables, motivated by recent progress in state-of-the-art quadratic solvers, and demonstrate how some additive-specific restrictions can be incorporated into mathematical optimization. While we show with numerical experiments that the proposed methods significantly reduce the required solution time for finding global optima compared to other formulations, we also observe that even with these new techniques and advanced computational resources, discrete modeling of frame structures remains a tremendously challenging problem.

We introduce a generalized value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. We describe its fundamental properties, which we exploit through three algorithms to calculate it. We then show how this generalized value function can be used to reformulate two classes of mixed-integer optimization problems: two-stage stochastic mixed-integer programming and multifollower bilevel mixed-integer programming. For both of these problem classes, the generalized value function approach allows the solution of instances that are significantly larger than those solved in the literature in terms of the total number of variables and number of scenarios.

Utilizing groundwater offers a promising solution to alleviate water stress in Ethiopia, providing a dependable and sustainable water source, particularly in regions with limited or unreliable surface water availability. However, effective decision-making regarding well drilling and placement is essential to maximize groundwater resource potential, enhancing agricultural productivity, reducing hunger, and bolstering food security in Ethiopia. This study concentrates on the development of two-stage stochastic mixed integer programming (SMIP) models to optimize well placement for sustainable agricultural irrigation, considering uncertain demand scenarios. Additionally, a deterministic mixed integer programming model is formulated for comparison with the two-stage SMIP. Experiments are conducted to explore various demand scenario distributions, revealing that the optimized total cost for the two-stage SMIP generally exceeds that of a deterministic setting, aligning with the two-stage SMIP’s focus on long-term benefits. Moreover, slight differences are observed in well layouts under different assumption scenarios. The study also examines the impact of selected parameters, such as fixed construction costs, per-meter drilling costs, and demand scenarios. The out-of-sample performance shows that the stochastic model is more flexible and resilient, with 11% and 4% lower costs than deterministic cases 1 and 3, respectively. This flexibility provides a more robust long-term strategy for well placement and resource allocation in groundwater management.

Purpose: This systematic review aims to critically evaluate the literature on the Generalized Bin Packing Problem (GBPP) and related problems, with an emphasis on their practical applications in logistics, manufacturing, and transportation.Design/methodology/approach: We reviewed recent papers published over the last eight years, from 2016 to January 2024, and systematically classified them based on the methods, techniques, models, and frameworks they employed. The studies are related to Operations Research, Engineering, Business, Manufacturing, or closely associated fields.Findings: The primary goal of our Systematic Literature Review (SLR) is to identify thematic areas addressed by recent research on the GBPP and its associated challenges. Notably, only 1.7% of the reviewed articles incorporate sustainability considerations. Packaging is another underexplored area although mentioned in several studies, few focus on optimizing packaging dimensions to facilitate palletization and improve space utilization.Originality/value: This article presents a comprehensive review of the literature on the Generalized Bin Packing Problem (GBPP) and related problems. We analyzed the distribution of publications by keyword, country, author and the quality of the papers. Our findings highlight the generality of the GBPP, as it encompasses various types of packing, cutting, and knapsack problems. We provide an in depth categorization of the GBPP and related problems based on problem type, solution techniques, and optimization criteria.

There is often a significant trade-off between formulation strength and size in mixed integer programming. When modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed precisely to these auxiliary continuous variables. For this reason, there has been considerable interest in constructing strong formulations that do not use continuous auxiliary variables. We introduce a technique to construct formulations without these detrimental continuous auxiliary variables. To develop this technique we introduce a natural non-polyhedral generalization of the Cayley embedding of a family of polytopes and show it inherits many geometric properties of the original embedding. We then show how the associated formulation technique can be used to construct small and strong formulation for a wide range of disjunctive constraints. In particular, we show it can recover and generalize all known strong formulations without continuous auxiliary variables.

Mixed integer programming (MIP) is commonly used to model indicator constraints, i.e., constraints that either hold or are relaxed depending on the value of a binary variable. Unfortunately, those models tend to lead to weak continuous relaxations and turn out to be unsolvable in practice; this is what happens, for e.g., in the case of Classification problems with Ramp Loss functions that represent an important application in this context. In this paper we show the computational evidence that a relevant class of these Classification instances can be solved far more efficiently if a nonlinear, nonconvex reformulation of the indicator constraints is used instead of the linear one. Inspired by this empirical and surprising observation, we show that aggressive bound tightening is the crucial ingredient for solving this class of instances, and we devise a pair of computationally effective algorithmic approaches that exploit it within MIP. One of these methods is currently part of the arsenal of IBM-Cplex  since version 12.6.1. More generally, we argue that aggressive bound tightening is often overlooked in MIP, while it represents a significant building block for enhancing MIP technology when indicator constraints and disjunctive terms are present.