Raymond Hemmecke
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Raymond Hemmecke has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Matthias Köppe
Department of Mathematics, University of California, Davis, California 95616
4 shared publications - Robert Weismantel
ETH Zurich Switzerland
2 shared publications - Bogdan Ichim1 shared publication
- Christof Soeger1 shared publication
Elke Eisenschmidt
1 shared publicationLyubov Romanchuk
Technion, Israel Institute of Technology
1 shared publication
Latest Publications
- 16 February 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 1-18
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- 16 February 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 1-18
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Open Access
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219--229], it was proved that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result [D.S. Hochbaum and J.G. Shanthikumar, Convex separable optimization is not much harder than linear optimization, J. ACM 37 (1990), 843--862], which allows us to use convex continuous optimization as a subroutine.
Open AccessGraver basis and proximity techniques for block-structured separable convex integer minimization problems
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219--229], it was proved that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result [D.S. Hochbaum and J.G. Shanthikumar, Convex separable optimization is not much harder than linear optimization, J. ACM 37 (1990), 843--862], which allows us to use convex continuous optimization as a subroutine.
- Open Access
- 20 October 2011
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 6 (2)
Computation of atomic fibers of Z-linear maps
For given matrix $A\in\Z^{d\times n}$, the set $P_{b}=\{z:Az=b,z\in\Z^n_+\}$ describes the preimage or fiber of $b\in\Z^d$ under the $\Z$-linear map $f_A:\Z^n_+\rightarrow\Z^d$, $x\mapsto Ax$. The fiber $P_{b}$ is called atomic, if $P_{b}=P_{b_1}+P_{b_2}$ implies $b=b_1$ or $b=b_2$. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, computational examples and applications are included as well.- 20 October 2011
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 6 (2)
Open AccessComputation of atomic fibers of Z-linear maps
For given matrix $A\in\Z^{d\times n}$, the set $P_{b}=\{z:Az=b,z\in\Z^n_+\}$ describes the preimage or fiber of $b\in\Z^d$ under the $\Z$-linear map $f_A:\Z^n_+\rightarrow\Z^d$, $x\mapsto Ax$. The fiber $P_{b}$ is called atomic, if $P_{b}=P_{b_1}+P_{b_2}$ implies $b=b_1$ or $b=b_2$. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, computational examples and applications are included as well. - Open Access
- 30 September 2011
- Published by Springer Nature in Mathematical Programming
- Vol. 137 (1-2) , 325-341
n-Fold integer programming in cubic time
- 30 September 2011
- Published by Springer Nature in Mathematical Programming
- Vol. 137 (1-2) , 325-341
Open Accessn-Fold integer programming in cubic time
- 12 August 2011
- Published by Springer Nature in Journal of Mathematical Chemistry
- Vol. 49 (10) , 2441-2456
Reconstructing biochemical cluster networks
- 12 August 2011
- Published by Springer Nature in Journal of Mathematical Chemistry
- Vol. 49 (10) , 2441-2456
Reconstructing biochemical cluster networks
- Open Access
Learning restricted Bayesian network structures
Bayesian networks are basic graphical models, used widely both in statistics and artificial intelligence. These statistical models of conditional independence structure are described by acyclic directed graphs whose nodes correspond to (random) variables in consideration. A quite important topic is the learning of Bayesian network structures, which is determining the best fitting statistical model on the basis of given data. Although there are learning methods based on statistical conditional independence tests, contemporary methods are mainly based on maximization of a suitable quality criterion that evaluates how good the graph explains the occurrence of the observed data. This leads to a nonlinear combinatorial optimization problem that is in general NP-hard to solve. In this paper we deal with the complexity of learning restricted Bayesian network structures, that is, we wish to find network structures of highest score within a given subset of all possible network structures. For this, we introduce a new unique algebraic representative for these structures, called the characteristic imset. We show that these imsets are always 0-1-vectors and that they have many nice properties that allow us to simplify long proofs for some known results and to easily establish new complexity results for learning restricted Bayes network structures.
Open AccessLearning restricted Bayesian network structures
Bayesian networks are basic graphical models, used widely both in statistics and artificial intelligence. These statistical models of conditional independence structure are described by acyclic directed graphs whose nodes correspond to (random) variables in consideration. A quite important topic is the learning of Bayesian network structures, which is determining the best fitting statistical model on the basis of given data. Although there are learning methods based on statistical conditional independence tests, contemporary methods are mainly based on maximization of a suitable quality criterion that evaluates how good the graph explains the occurrence of the observed data. This leads to a nonlinear combinatorial optimization problem that is in general NP-hard to solve. In this paper we deal with the complexity of learning restricted Bayesian network structures, that is, we wish to find network structures of highest score within a given subset of all possible network structures. For this, we introduce a new unique algebraic representative for these structures, called the characteristic imset. We show that these imsets are always 0-1-vectors and that they have many nice properties that allow us to simplify long proofs for some known results and to easily establish new complexity results for learning restricted Bayes network structures.
- 25 March 2010
- Published by Springer Nature in Journal of Mathematical Chemistry
- Vol. 48 (2) , 305-312
Decomposition of reaction networks: the initial phase of the permanganate/oxalic acid reaction
- 25 March 2010
- Published by Springer Nature in Journal of Mathematical Chemistry
- Vol. 48 (2) , 305-312
Decomposition of reaction networks: the initial phase of the permanganate/oxalic acid reaction
- Open Access
Challenging computations of Hilbert bases of cones associated with algebraic statistics
In this paper we present two independent computational proofs that the monoid derived from $5\times 5\times 3$ contingency tables is normal, completing the classification by Hibi and Ohsugi. We show that Vlach's vector disproving normality for the monoid derived from $6\times 4\times 3$ contingency tables is the unique minimal such vector up to symmetry. Finally, we compute the full Hilbert basis of the cone associated with the non-normal monoid of the semi-graphoid for $|N|=5$. The computations are based on extensions of the packages LattE-4ti2 and Normaliz.Open AccessChallenging computations of Hilbert bases of cones associated with algebraic statistics
In this paper we present two independent computational proofs that the monoid derived from $5\times 5\times 3$ contingency tables is normal, completing the classification by Hibi and Ohsugi. We show that Vlach's vector disproving normality for the monoid derived from $6\times 4\times 3$ contingency tables is the unique minimal such vector up to symmetry. Finally, we compute the full Hilbert basis of the cone associated with the non-normal monoid of the semi-graphoid for $|N|=5$. The computations are based on extensions of the packages LattE-4ti2 and Normaliz.