In the classical min-max approach to robust combinatorial optimization, a single feasible solution is computed that optimizes the worst case over a given set of considered scenarios. As is well known, this approach is very conservative, leading to solutions that in the average case are far from being optimal. In this paper, we present a … Read more
We study the classical 0-1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be … Read more
We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs … Read more
We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in R^n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the … Read more
We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion … Read more
An integer programming model for the truck dock assignment problem with operational time constraint within cross docks has been proposed in (Miao, Z.,Lim, A.,Ma, H., 2009. Truck dock assignment problem with operational time constraint within crossdocks. European Journal of Operational Research 192 (1), 105–115). We address the following issues in this formulation: 1) from among … Read more
This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled “Some continuous functions related to corner polyhedra I, II” [Math. Programming 3 (1972), 23-85, 359-389]. The survey presents the infinite group problem in the modern context … Read more
We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more
We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is \NPhard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the … Read more
The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too arti cial; (iii) are too homogeneous, not covering the wide range of characteristics found … Read more