My current research addresses questions in the area of discrete mathematics and optimization.
I am particularly interested in topics from integer programming, algorithmic discrete mathematics, and mixed integer and nonlinear optimization.
The second focus is on mathematics for studying questions in cell biology, systems biology, chemical engineering, and control theory.

Mixed Integer Linear Sets

From a practical perspective, mixed integer optimization represents a very powerful modeling paradigm. Its modeling power, however, comes with a price. The presence of both types of variables results in a significant increase in complexity with respect to geometric, algebraic, combinatorial and algorithmic properties. Specifically, the theory of cutting planes for mixed integer linear optimization is not yet at a similar level of development as in the pure integer case. The goal of this research is to examine a new geometric approach based on lattice point free polyhedra and use it to develop a cutting plane theory for mixed integer sets. We expect that these novel developments will naturally extend the theory that has been developed for the pure integer case and shed some light on the additional complexity that goes along with mixing discrete and continuous variables.
Recent work with colleagues and students includes investigations of the geometry of the integer points in a two- or higher dimensional cone rooted at a rational point [1,2,3] or the development of a general theory of disjunctive cutting planes for convex mixed integer sets based on excluding all points that do not lie in the interior of such a lattice point free set [4,5].

Literature

1. K. Andersen, Q. Louveaux, L. Wolsey, R. Weismantel, Inequalities from two rows of a simplex tableau, IPCO conference 2007, Lecture Notes in Computer Science 4513, Springer, 2007, 1 — 15.
2. K. Andersen, Q. Louveaux, R. Weismantel, Mixed integer sets associated with two linearly independent equations, Manuscript 2008.
3. K. Andersen, Ch. Wagner, R. Weismantel, On an analysis of the strength of mixed integer cutting planes from multiple simplex tableau rows, Manuscript 2008
4. K. Andersen, Q. Louveaux, R. Weismantel, An analysis of mixed integer points in convex sets, Manuscript 2008.
5. K. Andersen, Q. Louveaux, R. Weismantel, Certificates of linear mixed integer infeasibility, Operations Research Letters 36, 2008, 734 — 738.

Nonlinear Discrete Optimization

Discrete optimization problems are fundamental to basically every area of engineering and science. Such problems are typically very hard to solve and so the vast majority of literature has concentrated on linear cost functions. Our goal is to develop a comprehensive theory of Nonlinear Discrete Optimization, including the study of the underlying mathematical structures (algebraic, geometric and combinatorial), and the design of efficient algorithms for solution. This is an exciting area which is receiving increasing attention lately, due to recent advances in algebra and geometry which enable progress not possible before.
Recent work with colleagues includes minimization of polynomials over mixed-integer points in polyhedra using generating functions [3]; construction of test sets for nonlinear optimality [4]; a theory of N-fold optimization [6]; and studies of convex minimization and maximization for combinatorial problems such as matroids, matroid intersection, independence systems [1], [2], [5].

Literature

1. R. Hemmecke, M. Köppe, J. Lee, R. Weismantel, Nonlinear Discrete Optimization, Manuscript 2008, to appear in "50 years of integer programming", Springer Verlag.
2. J. Lee, S. Onn, R. Weismantel, Nonlinear Optimization over a Weighted Independence System, Manuscript 2008.
3. R. Hemmecke, M. Köppe, J. De Loera, R. Weismantel, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Mathematical Programming 115 (2), 2008, 273 — 290.
4. J. Lee, S. Onn, R. Weismantel, Test sets for nonlinear integer maximization, Operations Research Letters 36 (4), 2008, 439 — 443.
5. J. De Loera, R. Hemmecke, S. Onn, U.G. Rothblum, R. Weismantel, Convex Integer Maximization via Graver Bases, Journal of Pure and Applied Algebra, 2008, to appear.
6. R. Hemmecke, J. De Loera, S. Onn, R. Weismantel, N-fold Integer Programming, Discrete Optimization 5 (2), 2008, 231 —241.

Discrete Mathematics in Chemical Engineering and Control

The optimal design of processes from chemical engineering leads to mixed-integer nonlinear optimization problems (MINLP). As a first approach to solve these problems, local MINLP-solvers or stochastic procedures, like genetic algorithms, can be used. However, in both cases there is no guarantee that the global optimum is reached. In this project new methods for the global optimization of processes in chemical engineering are developed by engineers and mathematicians working hand in hand [1,2,3].
One approach is to investigate reformulation techniques in order to handle the original MINLP [4]. The quality of such reformulation strongly depends on efficient, problem specific under- and overestimators for nonlinear parts of the function [5,6]. For a global solution of the resulting convex relaxation, efficient algorithms based on cutting plane methods are to be developed. Analogously to the mixed-integer linear case the first question is to find appropriate lattice point free polyhedra on which bases cutting planes can be generated. Subsequently, it is to be investigated how efficient cutting planes can be extracted from these lattice point free polyhedra.

Literature

1. J. Gangadwala, A. Kienle, U.-U. Haus, D. Michaels, R. Weismantel, Global Bounds on Optimal Solutions for the Production of 2,3-Dimethylbutene-1, Industrial & Engineering Chemistry Research, 2006.
2. U.-U. Haus, D. Michaels, A. Seidel-Morgenstern, R. Weismantel, A method to evaluate the feasibility of TMB chromatography for reduced efficiency and purity requirements based on discrete optimization, Computers & Chemical Engineering 31 (11), 2007, 1525 — 1534.
3. J. Gangadwala, U.-U. Haus, M. Jach, A. Kienle, D. Michaels, R. Weismantel, Global analysis of combined reaction distillation processes, Computers & Chemical Engineering 32, 2008, 343 — 355.
4. U.-U. Haus, D. Michaels, A. Savchenko, Extended Formulations for MINLP Problems by Value Decompositions, Proceedings of the EngOpt 2008 conference, June 1–5, 2008, Rio de Janeiro, Brazil.
5. M. Jach, D. Michaels, R. Weismantel, Convex envelopes for (n-1)-convex functions, SIAM Journal on Optimization 19 (3), 2008, 1451 — 1466.
6. M. Jach, A. Kienle, D. Michaels, R. Weismantel, Novel convex underestimators and their application to the synthesis of combined reaction distillation processes, in Proc. of the European Symposium on Computer-Aided Process Engineering - 18, B. Braunschweig, X. Joulia (eds.), 2008.
7. Utz-Uwe Haus, Eckard Mayer, Jörg Raisch, Robert Weismantel, Throughput-optimal sequences for cyclically operated plants, Discrete Event Dynamic Systems, Vol. 18, No. 3, 2008, 355-383.

Discrete Mathematics in Cell and Systems Biology

A central problem in biology is to find suitable models for the structure of biological systems. To extract such a structure from experimental data is the network reconstruction problem. In this project a method [1] was developed that provably generates all alternatives for the structure of a biological network given a set of experimental data. All solutions agree with the experiments in structure and function.
In case of many different solutions (due to incomplete data) all solutions are classified and suggest additional experiments. One challenging task for future work is to discretize the data appropriately as it is usually measured in continuous concentrations. In [2] first practical applications with the group of Prof. Dr. W. Marwan can be found. An extension of the method with respect to dynamic behavior is introduced in [3,4].

In order to analyze signaling networks and understand their biological structure it is essential to find mathematical models. With the help of propositional logic and integer programming signaling networks can be described biologically meaningful [7]. In this project the two approaches are developed to answer questions like what are suitable intervention strategies or where are potential errors in the network. For the logical model a compression of the network could be proved [6] leading to a polynomial time algorithm to answer relevant questions. The methods are applied in the biological groups of Prof. Dr. B. Schraven [5] and Prof. Dr. M. Naumann.

Literature

1. W. Marwan, A. Wagler, R. Weismantel, A mathematical approach to solve the network reconstruction problem, Mathematical Methods of Operations Research 67 (1), 2008, 117 — 132.
2. M. Durzynski, W. Marwan, A. Wagler, R. Weismantel, Automatic Reconstruction of Molecular and Genetic Networks from Discrete Time Series Data, BioSystems 93, 2008, 181 — 190.
3. A. Wagler, R. Weismantel, The combinatorics of modeling and analyzing biological systems, NACO, 2008, to appear.
4. L. Torres, A. Wagler, R. Weismantel, Modeling the dynamic behavior of deterministic biological systems, in Proc. of ALIO-EURO 2008, Lecture Notes in Computer Science , Springer, 2008.
5. J. Saez-Rodriguez, L. Simeoni, J. Lindquist, R. Hemenway, U. Bommhardt, B. Arndt, U.-U. Haus, R. Weismantel, E.D. Gilles, S. Klamt, B. Schraven, A Comprehensive Logical Model Predicts Key Events in the T-cell Signaling Network, PLoS Computational Biology 3 (8), 2007, E163.
6. U.-U. Haus, K. Truemper, R. Weismantel, Linear Satisfiability Algorithm for 3CNF Formulas of Certain Signaling Networks Journal on Satisfyability, Boolean modeling and Computation 6, 2008, 13 — 32.
7. U.-U. Haus, K. Niermann, K. Truemper, R. Weismantel, Logic Integer Programming models for signaling networks, Journal of Computational Biology, to appear.