We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more
We present an end-to-end framework for generating solutions to combinatorial optimization problems with unknown components using transformer-based sequence-to-sequence neural networks. Our framework learns directly from past solutions and incorporates the known components, such as hard constraints, via a constraint reasoning module, yielding a constrained learning scheme. The trained model generates new solutions that are structurally … Read more
ArticleDownload View PDF
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 arises in many applications but is generally NP-hard, even for low-rank objectives. This paper introduces a set of broadly applicable conditions that certify when such problems are polynomially solvable. Our main condition is a new property of the feasible set, which we term co-monotonicity. We show that this property holds for two important … 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