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
We study constant-factor approximation algorithms for the Bin Packing Problem with Setups (BPPS). First, we show that adaptations of classical BPP heuristics can have arbitrarily poor worst-case performance on BPPS instances. Then, we propose a two-phase heuristic for the BPPS that applies an α-approximation algorithm for the BPP to the items of each class and … 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
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 Tower Defense (TD) games, the objective is to defend a specific point on the game map from mobile units by constructing towers with offensive capabilities. In this work, we focus on Bloons Tower Defense (Bloons TD), one of the earliest and most prominent TD games. We show that the problem of finding tower configurations … Read more
We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items. In the first stage, we select the optimal dimensions of the boxes, while in the second … Read more
We consider bilevel programs that involve a leader, who first commits to a mixed-integer decision, and a follower, who observes this decision and then responds rationally by solving a linear program (LP). Standard approaches often reformulate these bilevel optimization problems as single-level mixed-integer programs by exploiting the follower’s LP optimality conditions. These reformulations introduce either … Read more
Recently robust combinatorial optimization problems with budgeted interdiction uncertainty affecting cardinality-based constraints or objective were considered by presenting, comparing and experimenting with compact formulations. In this paper we present a compact formulation for the case in which locally budgeted interdiction uncertainty affects the objective function and covering constraints simultaneously. ArticleDownload View PDF
We study the combinatorial structure of a quadratic set function $F(S)$ arising from a class of binary optimization models within the family of undesirable facility location problems. Despite strong empirical evidence of nested optimal solutions in previously studied real-world instances, we show that $F(S)$ is, in general, neither submodular nor supermodular. To quantify deviation from … Read more