Submodularity, a discrete analog of convexity, is a key property in discrete optimization that features in the construction of valid inequalities and analysis of the greedy algorithm. In this paper, we broaden the approximate submodularity literature, which so far has largely focused on variants of greedy algorithms and iterative approaches. We define metrics that quantify … Read more
Rank aggregation is widely used in group decision-making and many other applications where it is of interest to consolidate heterogeneous ordered lists. Oftentimes, these rankings may involve a large number of alternatives, contain ties, and/or be incomplete, all of which complicate the use of robust aggregation methods. In particular, these characteristics have limited the applicability … Read more
Connectivity is a central concept in combinatorial optimization, graph theory, and operations research. In many applications, one is interested in finding an optimal subset of vertices with the essential requirement that the vertices are connected, but not how they are connected. I.e., it is not relevant, which edges are selected to obtain connectivity. Two natural … Read more
In this paper, we consider the (additive integrality) gap of the cutting stock problem (CSP) and the skiving stock problem (SSP). Formally, the gap is defined as the difference between the optimal values of the ILP and its LP relaxation. For both, the CSP and the SSP, this gap is known to be bounded by … Read more
A natural and important generalization of submodularity—$k$-submodularity—applies to set functions with $k$ arguments and appears in a broad range of applications, such as infrastructure design, machine learning, and healthcare. In this paper, we study maximization problems with $k$-submodular objective functions. We propose valid linear inequalities, namely the $k$-submodular inequalities, for the hypograph of any $k$-submodular … Read more
Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more
We consider a single machine scheduling problem to minimize the completion time variance of n jobs. This problem is known to be NP-hard and our contribution is to establish a novel bounding condition for a characterization of an optimal sequence. Specifically, we prove a necessary and sufficient condition (which can be verified in O(n\log n)) … Read more
We consider the class of 2-partition inequalities for the clique partitioning problem associated with complete graphs. We propose a heuristic separation algorithm for the inequalities and evaluate its usefulness in a cutting-plane algorithm. Our computational experiments fall into two parts. In the first part, we compare the LP objective values obtained by the proposed separator … Read more
In this paper we introduce the selective maximum coverage and the selective maximum set packing problem and variants of them. Both problems are strongly related to well studied problems such as maximum coverage, set packing, and (bipartite) hypergraph matching. The two problems are given by a collection of subsets of a ground set and index … Read more
This paper introduces the production routing problem for perishable products with fixed shelf life and gradual decay, where the age of products impacts the price that can be obtained when satisfying customer demands. In this problem, a single supplier is responsible for the production and distribution of perishable products to a set of customers. Fixed … Read more