The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing — referred to as graph matching — and an inherent optimization problem known … Read more
In the surface mining industry, the Equipment Selection Problem involves choosing an appropriate fleet of trucks and loaders such that the long-term mine plan can be satisfied. An important characteristic for multi-location (multi-location and multi-dumpsite) mines is that the underlying problem is a multi-commodity flow problem. The problem is therefore at least as difficult as … Read more
This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate … Read more
Hub location problems are strategic network planning problems. They formalise the challenge of mutually exchanging shipments between a large set of depots. The aim is to choose a set of hubs (out of a given set of possible hubs) and connect every depot to a hub so that the total transport costs for exchanging shipments … Read more
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 propose a framework to model general guillotine restrictions in two-dimensional cutting problems formulated as Mixed Integer Linear Programs (MIP). The modeling framework requires a pseudo-polynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within … Read more
We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to hard nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the … 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
In this note we announce the availability of an electronic compendium of extreme functions for Gomory–Johnson’s infinite group problem. These functions serve as the strongest cut-generating functions for integer linear optimization problems. We also close several gaps in the literature. ArticleDownload View PDF
In this paper we consider an aggregation technique introduced by Yildiran, 2009 to study the convex hull of regions defined by two quadratic or by a conic quadratic and a quadratic inequality. Yildiran shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities (LMI). We … Read more