Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142025 | Operations Research Letters | 2016 | 6 Pages |
Abstract
We consider the problem of optimizing a linear rational function subject to totally unimodular (TU) constraints over {0,1} variables. Such formulations arise in many applications including assortment optimization. We show that a natural extended LP relaxation of the problem is “tight”. In other words, any extreme point corresponds to an integral solution. We also consider more general constraints that are not TU but obtained by adding an arbitrary constraint to the set of TU constraints. Using structural insights about extreme points, we present a polynomial time approximation scheme (PTAS) for the general problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vashist Avadhanula, Jalaj Bhandari, Vineet Goyal, Assaf Zeevi,