Abstract: This paper introduces an exact algorithm for solving integer programs, neither using cutting planes nor enumeration techniques. It is a primal augmentation algorithm that relies on iteratively substituting one column by columns that correspond to irreducible solutions of certain linear diophantine inequalities. We demonstrate the algorithm's potential by testing it on some instances of the MIPLIB with up to 6000 variables.
Preprint (Postscript), BibTeX entry, Springer LINK with PDFThis is the conference version of the paper On the Way to Perfection: Primal Operations for Stable Sets in Graphs.
Abstract: This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.
Preprint (Postscript), Springer LINK with PDF
Abstract: In this paper some operations are described that transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. These operations yield a purely combinatorial augmentation procedure for finding a maximum weighted stable set in a graph. Starting with a stable set in a given graph one defines a simplex type tableau whose associated basic feasible solution is the incidence vector of the stable set. In an iterative fashion, non-basic columns that would lead to pivoting into non-integral basic feasible solutions, are replaced by new columns that one can read off from special graph structures such as odd holes, odd antiholes, and various generalizations. Eventually, either a pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.
Preprint (Postscript)Abstract: This paper is concerned with the computer-aided optimal design of reaction-destillation processes. The production of solvent 2,3-dimethylbutene-1 by isomerization of 2,3-dimethylbutene-2 is considered as an innovative benchmark problem. Possible process candidates are a reactive distillation column, a reactor coupled to a nonreactive distillation column or a reactive reboiler with a nonreactive distillation column on top. Local MINLP optimization indicates that the reactive distillation has the lowest total annualized costs. However, due to the non-convexity of the underlying mathematical problem better solutions for the other process candidates cannot be excluded. For this purpose a new global approach is proposed which is based on discrete optimization of the underlying model equations and which proves globally that reactive distillation is the best option.
Elsevier link, BibTeX entryAbstract: This paper considers the problem of approximating a given crystallite orientation distribution function (codf) by a set of texture components. Problems of this type are of importance if the crystallographic texture has to be taken into account in finite element simulations of metal forming operations. The equivalence of this task to a Mixed Integer Quadratic Programming problem (MIQP) is shown. Special emphasis is given to the generation of a class of approximations with an increasing number of texture components. Furthermore, the constraints resulting from the nonnegativity, the normalization, and the symmetry of the codf are analyzed. Finally, a set of approximations of three different experimental textures determined with this solution scheme is presented and discussed. Based on these hierarchic solutions, the engineer can decide how detailed the microstructure is considered.
Elsevier link, BibTeX entryAbstract: This paper is concerned with computer-aided optimal design of combined reaction-distillation processes. The production of solvent 2,3-dimethylbutene-1 by isomerization of 2,3-dimethylbutene-2 is considered as an innovative benchmark problem. Possible process candidates are a reactive distillation column, a reactor coupled to a nonreactive distillation column, or a reactive reboiler with a nonreactive distillation column on top. Suitable mathematical models of the different processes are formulated, and the reaction kinetics of the isomerization over an Amberlyst 15 catalyst is determined. Local mixed-integer nonlinear optimization indicates that reactive distillation has the lowest total annualized costs. However, because of the nonconvexity of the underlying optimization problem, better solutions for the other process candidates cannot be excluded with the local approach. Therefore, a new approach is presented which provides a global lower bound for the second best solution and therefore proves that reactive distillation is the best option. The new approach is based on some suitable polyhedral approximation of the underlying model equations leading to a mixed-integer linear optimization problem.
ACM link, BibTeX entryAbstract: In this paper a new approach for computing global bounds on optimal solutions of mixed-integer nonlinear programs is presented. These type of problems frequently arise in optimal design of chemical processes. The approach is based on a hierarchy of polyhedral relaxations leading to mixed-integer linear programs, which can be solved rigorously. Application is demonstrated for the optimal design of combined reaction distillation processes and for feasibility studies of simulated moving bed chromatographic processes.
Elsevier link, BibTeX entryAlready available online as DOI:10.1016/j.compchemeng.2007.01.001.
Abstract: This paper introduces an exact mathematical approach based on combinatorial optimization to analyze continuous linear countercurrent chromatographic processes. The analysis is based on a given set of input parameters including, in particular, purity requirements and number of plates per zone. As an outcome of the analysis either a proof of infeasibility is derived for a given set of parameters, or a feasible solution is found that is in correspondence with the input requirements. Details regarding the mathematical combinatorial subproblems are presented.
BibTeX entryAlready available online as DOI:10.1016/j.compchemeng.2007.04.015.
Abstract: Polyhedral relaxation is a powerful tool for determining global bounds on optimal solutions in chemical process synthesis. Combined reaction distillation processes are considered as a challenging application example. To reduce complexity of the resulting mixed integer linear optimization problems model reduction by means of wave functions is proposed and polyhedral relaxations of sigmoidal wave functions in two variables are derived. It is shown that these relaxations provide better approximation quality than approximating the composed functions individually. Further, the concave envelope of such functions is characterized and (non-linear) convex underestimators are derived. The approximation results are employed in the computation of lower bounds on the vapor flow of a combined reaction distillation process with a metathesis reaction 2B$\leftrightharpoons$A+C. We restrict computations to a domain around a known local optimum, trading computation time for some of the globality. This still proves of a bound on the vapor flow, but for restricted operating conditions of the column.
BibTeX entryAvailable online as doi:10.1371/journal.pcbi.0030163.
Abstract: T-lymphocytes are central regulators of the adaptive immune response and their inappropriate activation can cause autoimmune diseases or cancer. The understanding of the signalling mechanisms underlying T cell activation is a prerequisite to develop new strategies for pharmacological intervention and disease treatments. However, much of the existing literature on T cell signalling is related to T-cell development or to activation processes in transformed T-cell lines (e.g. Jurkat), whereas information on non-transformed primary T-cells is limited. Here, immunologists and theoreticians have compiled data from the existing literature that stem from analysis of primary T cells. They used this information to establish a qualitative Boolean network that describes T-cell activation mechanisms after engagement of the TCR, the CD4/CD8 co-receptors and CD28. The network comprises 94-nodes and can be extended to facilitate interpretation of new data that emerge from experimental analysis of T-cell activation. Newly developed tools and methods allow in silico analysis and manipulation of the network and can uncover hidden/unforeseen signalling pathways. Indeed, by assessing signalling events controlled by CD28 and the protein tyrosine kinase Fyn the authors show that computational analysis of even a qualitative network can provide new and non-obvious signalling pathways which can be validated experimentally.
Abstract: In this paper, we present a method to determine globally optimal schedules for cyclically operated plants where activities have to be scheduled on limited resources. In cyclic operation, a large number of entities is processed in an identical time scheme. For strictly cyclic operation, where the time offset between entities is also identical for all entities, the objective of maximizing throughput is equivalent to the minimization of the cycle time. The resulting scheduling problem is solved by deriving a mixed integer optimization problem from a discrete event model. The model includes timing constraints as well as open sequence decisions for the activities on the resources. In an extension, hierarchical nesting of cycles is considered, which often allows for schedules with improved throughput. The method is motivated by the application to high throughput screening plants, where a specific combination of requirements has to be obeyed (e. g. revisited resources, absence of buffers, or time window constraints)
BibTeX entryAbstract: Given a metabolic network in terms of its metabolites and reactions, our goal is to efficiently compute the minimal knock out sets of reactions required to block a given behaviour. We describe an algorithm which improves the computation of these knock out sets when the elementary modes (minimal functional subsystems) of the network are given. We also describe an algorithm which computes both the knock out sets and the elementary modes containing the blocked reactions directly from the description of the network and whose worst-case computational complexity is better than the algorithms currently in use for these problems. Computational results are included.
ArXiV linkAbstract: This paper deals with algorithmic issues related to the design of an augmentation algorithm for general and 0/1-integer programs. We recall the approach of integer pivoting and introduce the family of Gomory-Young augmentation vectors that can be derived from a simplex tableau. Furthermore, a technique of combining Gomory-Young vectors and combinatorial augmentation vectors in one augmentation scheme is presented. Two computational experiments demonstrate the potential of pivoting in an integer fashion.
Technical Report (Postscript)