We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory–Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test. Citation6 pages extended abstract to appear in Proc. LAGOS 2017, with 21 pages of appendix.ArticleDownload View PDF
The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more
Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more
A large number of the real world planning problems which are today solved using Operations Research methods are actually multi-objective planning problems, but most of them are solved using single-objective methods. The reason for converting, i.e. simplifying, multi- objective problems to single-objective problems is that no standard multi-objective solvers exist and specialized algorithms need to … Read more
We consider the problem of packing congruent circles with the maximum radius in a unit square. As a mathematical program, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem which possesses a large number of local optima. We study several convexification techniques for the circle packing problem, including polyhedral and semi-definite relaxations and … Read more
The generalized intersection cut (GIC) paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure … Read more
We study a multiechelon supply chain model that consists of a production level and several transportation levels, where the demands can exist in the production echelon as well as any transportation echelons. With the presence of stationary production capacity and general cost functions, our model integrates production, inventory and transportation decisions and generalizes existing literature … Read more
The infinite models in integer programming can be described as the convex hull of some points or as the intersection of half-spaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to … Read more
We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing … Read more
Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a … Read more