The Experts below are selected from a list of 291 Experts worldwide ranked by ideXlab platform
Shmuel Onn - One of the best experts on this subject based on the ideXlab platform.
-
An Algorithmic Theory of Integer Programming
arXiv: Optimization and Control, 2019Co-Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-manuel Klein, Martin Koutecký, Asaf Levin, Shmuel OnnAbstract:We study the general Integer Programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that Integer Programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is the binary encoding length of the input. In particular, Integer Programming is fixed-parameter tractable parameterized by $a$ and $d$, and is solvable in polynomial time for every fixed $a$ and $d$. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time $g(a,d)\textrm{poly}(n)$, independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix $A$, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of Integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured Integer programs. In particular, we develop near-linear time algorithms for $n$-fold, tree-fold, and $2$-stage stochastic Integer programs. We also discuss some of the many applications of these classes.
-
Robust Integer Programming
arXiv: Optimization and Control, 2014Co-Authors: Shmuel OnnAbstract:We provide a complexity classification of four variants of robust Integer Programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multidimensional transportation, and describe an effective parametrization of robust Integer Programming.
-
Robust Integer Programming
Operations Research Letters, 2014Co-Authors: Shmuel OnnAbstract:We provide a complexity classification of four variants of robust Integer Programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multiway statistical table problems, and describe an effective parametrization of robust Integer Programming.
-
n-Fold Integer Programming in cubic time
Mathematical Programming, 2011Co-Authors: Raymond Hemmecke, Shmuel Onn, Lyubov RomanchukAbstract:n-Fold Integer Programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of Integer Programming. The fastest algorithm for n-fold Integer Programming predating the present article runs in time \({O \left(n^{g(A)}L\right)}\) with L the binary length of the numerical part of the input and g(A) the so-called Graver complexity of the bimatrix A defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time O (n3L) having cubic dependency on n regardless of the bimatrix A. Our algorithm works for separable convex piecewise affine objectives as well. Moreover, it can be used to define a hierarchy of approximations for any Integer Programming problem.
-
The Graver Complexity of Integer Programming
Annals of Combinatorics, 2009Co-Authors: Yael Berstein, Shmuel OnnAbstract:In this article we establish an exponential lower bound on the Graver complexity of Integer programs. This provides new type of evidence supporting the presumable intractability of Integer Programming. Specifically, we show that the Graver complexity of the incidence matrix of the complete bipartite graph K 3,m satisfies g(m) = Ω(2 m ), with g(m) ≥ 17·2 m−3 –7 for every m > 3.
Rüdiger Schultz - One of the best experts on this subject based on the ideXlab platform.
-
Stochastic Integer Programming
Handbooks in Operations Research and Management Science, 2003Co-Authors: François V. Louveaux, Rüdiger SchultzAbstract:Abstract When introducing Integer variables into traditional linear stochastic programs structural properties and algorithmic approaches have to be rethought from the very beginning. Employing basics from parametric Integer Programming and probability theory we analyze the structure of stochastic Integer programs. In the algorithmic part of the paper we review solution techniques from Integer Programming and discuss their impact on the specialized structures met in stochastic Programming.
-
dual decomposition in stochastic Integer Programming
Operations Research Letters, 1999Co-Authors: Claus C Caroe, Rüdiger SchultzAbstract:We present an algorithm for solving stochastic Integer Programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-Integer variables in each time stage. Numerical experience is presented for some two-stage test problems.
Pamela H. Vance - One of the best experts on this subject based on the ideXlab platform.
-
Formulating a Mixed Integer Programming Problem to Improve Solvability
Operations Research, 1993Co-Authors: Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Gabriele Sigismondi, Pamela H. VanceAbstract:A standard formulation of a real-world distribution problem could not be solved, even for a good solution, by a commercial mixed Integer Programming code. However, after reformulating it by reducing the number of 0-1 variables and tightening the linear Programming relaxation, an optimal solution could be found efficiently. The purpose of this paper is to demonstrate, with a real application, the practical importance of the need for good formulations in solving mixed Integer Programming problems.
Sudarsan Nanda - One of the best experts on this subject based on the ideXlab platform.
-
On a pair of nonlinear mixed Integer Programming problems
European Journal of Operational Research, 2011Co-Authors: M.s. Mishra, D. Acharya, Sudarsan NandaAbstract:Abstract We consider maximin and minimax nonlinear mixed Integer Programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed Integer Programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed Integer Programming.
George L. Nemhauser - One of the best experts on this subject based on the ideXlab platform.
-
50 Years of Integer Programming 1958-2008 - 50 Years of Integer Programming 1958-2008
2009Co-Authors: Michael Jünger, George L. Nemhauser, Thomas M. Liebling, Denis Naddef, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A WolseyAbstract:In 1958, Ralph E. Gomory transformed the field of Integer Programming when he published a paper that described a cutting-plane algorithm for pure Integer programs and announced that the method could be refined to give a finite algorithm for Integer Programming. In 2008, to commemorate the anniversary of this seminal paper, a special workshop celebrating fifty years of Integer Programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop. It contains reprints of key historical articles and written versions of survey lectures on six of the hottest topics in th
-
Formulating a Mixed Integer Programming Problem to Improve Solvability
Operations Research, 1993Co-Authors: Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Gabriele Sigismondi, Pamela H. VanceAbstract:A standard formulation of a real-world distribution problem could not be solved, even for a good solution, by a commercial mixed Integer Programming code. However, after reformulating it by reducing the number of 0-1 variables and tightening the linear Programming relaxation, an optimal solution could be found efficiently. The purpose of this paper is to demonstrate, with a real application, the practical importance of the need for good formulations in solving mixed Integer Programming problems.
