We present a constructive procedure for certifying the infeasibility of a mixed-integer program (MIP) using recursion on a sequence of sets that describe the sets of barely feasible right-hand sides. Each of these sets corresponds to a monotonic superadditive function, and the pointwise limit of this sequence is a functional certificate for MIP infeasibility. Our … Read more
ArticleDownload View PDF
Probing is an important presolving technique in mixed-integer programming solvers. It selects binary variables, tentatively fixes them to 0 and 1, and performs propagation to deduce additional variable fixings, bound tightenings, substitutions, and implications. In this work, we propose clique probing instead of probing on individual variables, we select cliques, a set of binary variables … Read more
Convex maximization encompasses a broad class of optimization problems and is generally $\mathsf{NP}$-hard, even for low-rank objectives. While polynomial solvability has been established for several important special cases, a broader structural understanding for mixed-integer settings remains limited. In this paper, we study this question from a geometric perspective and identify a structural property of the … Read more
This paper addresses an operational planning challenge in two-tier robotized sorting systems (T-RSS), an emerging alternative to traditional conveyor-based sorting in e-commerce delivery stations. Designed to be compact and space-efficient, T-RSS use an upper tier to sort parcels from loading stations to drop-off points, which connect to roll containers on a lower tier where parcels … Read more
When optimizing a nonlinear objective, one can employ a neural network as a surrogate for the nonlinear function. However, the resulting optimization model can be time-consuming to solve globally with exact methods. As a result, local search that exploits the neural-network structure has been employed to find good solutions within a reasonable time limit. For … Read more
Capacity Planning problems are a class of optimization problems used in diverse industries to improve resource allocation and make investment decisions. Solving real-world instances of these problems typically requires significant computational effort. To tackle this, we propose machine-learning-aided column generation methods for solving large-scale capacity planning problems. Our goal is to accelerate column generation by … Read more
This paper surveys optimization problems arising in agriculture, energy systems, and water-energy coordination from an operations research perspective. These problems are commonly formulated as integer nonlinear programs, mixed-integer nonlinear programs, or combinatorial set optimization models, characterized by nonlinear physical constraints, discrete decisions, and intertemporal coupling. Such structures pose significant computational challenges in large-scale and repeated-solution … Read more
This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear … Read more
In this paper, we propose an extension of the classical weight reduction inequalities for the binary knapsack polytope for settings where the maximum-weight item in the associated pack is not unique. We derive sufficient conditions under which the extended inequalities are facet-defining and identify conditions under which they strictly dominate the original weight reduction inequalities. … Read more