This paper studies the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as one resulting from the intersection of two subproblems. … Read more
We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether … Read more
Making cut generating functions (CGFs) computationally viable is a central question in modern integer programming research. One would like to nd CGFs that are simultaneously good, i.e., there are good guarantees for the cutting planes they generate, and ecient, meaning that the values of the CGFs can be computed cheaply (with procedures that have some … Read more
In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study … Read more
This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework formulates these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest path problem in an auxiliary network. We design tools and techniques for exploiting the network model in … Read more
Many problems in real life have more than one decision criterion, referred to as multi-objective optimization (MOO) problems, and the objective functions of these problems are conflicting in most cases. Hence, finding non-dominated solutions is very critical for decision making process. Tri-objective mixed-integer linear programs (TOMILP) are an important subclass of MOOs that are applicable … Read more
This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. … Read more
Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal … Read more
In this paper, we develop a new algorithmic framework that handles black box problems with integer variables. The strategy included in the framework makes use of specific search directions (so called primitive directions) and a suitably developed nonmonotone line search, thus guaranteeing a high level of freedom when exploring the integer lattice. We first describe … Read more
We prove that every pointed closed convex set in $\mathbb{R}^n$ is the intersection of all the rational closed halfspaces that contain it. This generalizes a previous result by the authors for compact convex sets. Citation arXiv:1802.03296. February 2018 Article Download View Pointed Closed Convex Sets are the Intersection of All Rational Supporting Closed Halfspaces