This paper investigates the a-posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree’s branching … Read more
Algorithms for continuous optimization problems have a rich history of design and innovation over the past several decades, in which mathematical analysis of their convergence and complexity properties plays a central role. Besides their theoretical properties, optimization algorithms are interesting also for their practical usefulness as computational tools for solving real-world problems. There are often … Read more
Benders decomposition is a technique to solve large-scale mixed-integer optimization problems by decomposing them into a pure-integer master problem and a continuous separation subproblem. To accelerate convergence, we propose Random Partial Benders Decomposition (RPBD), a decomposition method that randomly retains a subset of the continuous variables within the master problem. Unlike existing problem-specific approaches, RPBD … Read more
TitleDiscovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling Authorsİbrahim Oğuz Çetinkaya^1; İ. Esra Büyüktahtakın^1*; Parshin Shojaee^2; Chandan K. Reddy^2 Affiliations^1 Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA^2 Department of Computer Science, Virginia Tech, Arlington, VA, USA Abstract: Our study contributes to the scheduling and combinatorial optimization … Read more
We present a simplified proof of Lagrange’s theorem using only elementary properties of sets and sequences. ArticleDownload View PDF
We introduce the Expeditionary Logistics Network Design Problem (ELNDP), a new formulation for operational-level planning in expeditionary environments where multi-modal vehicle coordination is critical and penalties for unmet demand dominate transportation costs. ELNDP extends the classical Scheduled Service Network Design Problem by incorporating flexible commodity sourcing and heterogeneous vehicle capabilities, both essential in military logistics. … Read more
Selecting an effective step-size is a fundamental challenge in first-order optimization, especially for problems with non-Euclidean geometries. This paper presents a novel adaptive step-size strategy for optimization algorithms that rely on linear minimization oracles, as used in the Conditional Gradient or non-Euclidean Normalized Steepest Descent algorithms. Using a simple heuristic to estimate a local Lipschitz … Read more
Counterfactual explanations (CEs) offer a human-understandable way to explain decisions by identifying specific changes to the input parameters of a base or present model that would lead to a desired change in its outcome. For optimization models, CEs have primarily been studied in limited contexts, such as linear optimization problems with continuous decision variables or … Read more
Column liquid chromatography is an important technique applied in the production of biopharmaceuticals, specifically for the separation of biological macromolecules such as proteins. When setting up process conditions, it is crucial that the purity of the product is sufficiently high, even in the presence of perturbations in the process conditions, e.g., altered buffer salt concentrations. … Read more
We present a new difference of convex functions algorithm (DCA) for solving linear and nonlinear mixed complementarity problems (MCPs). The approach is based on the reformulation of bilinear complementarity constraints as difference of convex (DC) functions, more specifically, the difference of scalar, convex quadratic terms. This reformulation gives rise to a DC program, which is … Read more