Combinatorial Optimization

Facility Location with Decision-Dependent Scenario Probabilities: Linked Lifted Cuts and a Scenario-Decomposed Branch-and-Cut

Categories Applications - OR and Management Sciences, Combinatorial Optimization, Stochastic Programming Tags , , , , , , , , ,

We study two-stage facility location in which the probability of each demand scenario is an affine function of the opening decisions, so the objective multiplies a decision-dependent probability by a decision-dependent recourse value and is bilinear in the binary first stage. The standard treatment linearizes these products with McCormick envelopes over global bounds on the … Read more

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases

Categories Combinatorial Optimization, Graphs and Matroids Tags , ,

Let \(M\) be a matroid, let \(\ell:E(M)\to G\) be a labeling of its elements by an abelian group, and let \(F\subseteq G\) be finite. A base is \emph{\(F\)-avoiding} if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost \(F\)-avoiding base can be obtained from any min-cost … Read more

A heuristic framework for a class of vehicle routing problems

Categories Combinatorial Optimization, Meta Heuristics, Transportation Tags , , ,

We propose GenericILS, a general-purpose heuristic framework for generating high-quality upper bounds for Vehicle Routing Problems whose pricing subproblems are modeled, in column-generation-based exact algorithms, as resource-constrained shortest path problems described through Resource Extension Functions (REFs), the standard device for encoding constraints in branch-and-price algorithms. GenericILS reuses REFs implemented for the exact method, without a … Read more

Reinforcing Old Fences Gives New Facets and More

Categories Combinatorial Optimization, Integer Programming, Polyhedra

The unpublished 1990 technical report reproduced here introduced the $t$-reinforced $k$-fence inequalities, the first facets of the acyclic subgraph polytope that are not rank inequalities: each simple $k$-fence induces $k-2$ of them, one for each $1\le t\le k-2$. The report proved this with the spectral method, using a coherent configuration and computer algebra. It went … Read more

solving the multi-objective integer minimum cost flow problem via circulations

Categories Combinatorial Optimization, Multi-Criteria Optimization, Network Optimization Tags , ,

The Multi-objective Integer Minimum Cost Flow Problem (MOIMCF) asks for the efficient integer flows of a capacitated network whose arcs carry vectors of conflicting costs. We present an exact algorithm that computes a minimal complete set of efficient flows, based on a characterization of efficiency by circulations in the residual network. The feasible set is … Read more

Beyond Local Influence: Improved Bounds, Exact Models and Efficient Algorithms for Component-Based Diffusion in Networks

Categories Combinatorial Optimization, Network Optimization Tags , ,

Diffusion in networks is often modeled as a local neighbor-based process: a node becomes active as a result of influence exerted by its active neighbors. However, in many technological and communication settings, adoption is driven not only by local influence, but by access to sufficiently large active connected regions. This paper studies such component-based diffusion … Read more

Sharp proximity for group-labeled matroid bases

Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , ,

Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We give an alternative proof of the sharp unweighted proximity bound established by Lizhong Chen: for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. … Read more

A sharp local threshold for integer feasibility in three-way transportation polytopes

Categories Integer Programming, Polyhedra Tags , , , , , ,

Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more

A regular perspective on solving the irregular strip packing problem with the dotted-board model: a mosaic approach and a divide-and-conquer strategy

Categories Combinatorial Optimization, Integer Programming Tags , , , ,

Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems

Categories Cutting Plane Approaches, Integer Programming, Polyhedra Tags , , , , , ,

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal–Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP ∩ coNP, so it … Read more