Publications

by Hermann Schichl

Books



H. Schichl and R. Steinbauer, Einführung in das mathematische Arbeiten, zweite erweiterte Auflage, Springer Verlag, 2012
Homepage,


H. Schichl and R. Steinbauer, Einführung in das mathematische Arbeiten, Springer Verlag, 2009
Homepage,


Manuscripts



H. Schichl and M. C. Markót, Interval Analysis on Directed Acyclic Graphs for Global Optimization. Higher Order Methods, pdf file (244K),
A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation.

Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation of higher order. It is shown how to combine this with constraint propagation techniques and graph coloring to efficiently produce narrower interval Hessians and second order slopes, as well as third order derivative tensors than those provided by using only interval automatic differentiation preceded by constraint propagation. We also construct quadratic relaxations of nonlinear optimization problems of the same dimension as the original problem, which have a second order approximation property.


H. Schichl and M. C. Markót, Optimal Enclosures of Derivatives and Slopes for Univariate Functions, pdf file (244K),
For univariate factorable functions we provide algorithms which compute optimal enclosures for ranges, derivatives of arbitrarily high order, and slopes up to second order.


H. Schichl and A. Neumaier, Transposition Theorems and Hypernorms, pdf file (244K),
We prove new transposition theorems which are connected to hypernorm estimates.


Papers submitted for publication



A. Baharev, A. Neumaier, and H. Schichl, Tearing systems of nonlinear equations II. A practical exact algorithm, Manuscript (2017).


A. Baharev, A. Neumaier, and H. Schichl, Tearing systems of nonlinear equations I. A survey, Manuscript (2017).


A. Baharev, A. Neumaier, and H. Schichl, An exact method for the minimum feedback arc set problem, Manuscript (2017).


H Fendl, H Schichl, A feasible second order bundle algorithm for nonsmooth, nonconvex optimization problems with inequality constraints: I. Derivation and convergence, arXiv preprint arXiv:1506.07937, 2015, arxiv.org


H Fendl, H Schichl, A feasible second order bundle algorithm for nonsmooth nonconvex optimization problems with inequality constraints: II. Implementation and numerical results, arXiv preprint arXiv:1506.08021, 2015, arxiv.org


M Sellmann, H Schichl, Consensual Affine Transformations for Aggregation of Partial Valuations, Manuscript (2018)


Papers accepted for publication



H. Schichl, Mathematical Modeling and Global Optimization, Habilitation Thesis, draft of a book, Cambridge Univ. Press, to appear.
ps file (7600K), pdf file (2400K),
downloading/printing problems?
Optimization addresses the problem of finding the best possible choices with respect to a given target, not violating a number of restrictions

In mathematical terms, optimization is the problem of minimizing (or maximizing) a prescribed function, the objective function, while obeying a number of equality and inequality constraints Depending on the area of definition of these functions, one can differentiate various classes of optimization problems, continuous problems, discrete problems, and mixed-integer problems.

The full version of the abstract is here.


Published papers



A. Baharev, A. Neumaier, H. Schichl. Failure Modes of Tearing and a Novel Robust Approach, Linköping Electronic Conference Proceedings, (132), 353-362. (2017), DOI: 10.3384/ecp17132353


H. Fendl, A. Neumaier and H. Schichl, Certificates of infeasibility via nonsmooth optimization, J. Global Optimization 69 (2017), 157-182. (published online 28 October 2016), pdf file,
An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points. This paper presents a certificate of infeasibility for finding such boxes by solving a linearly constrained nonsmooth optimization problem. Furthermore, the constructed certificate can be used to enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem.


Ali Baharev, Hermann Schichl, Endre Rév, Computing the noncentral-F distribution and the power of the F-test with guaranteed accuracy, Computational Statistics (2016), DOI: 10.1007/s00180-016-0701-3 online publication
The computations involving the noncentral-F distribution are notoriously difficult to implement properly in floating-point arithmetic: Catastrophic loss of precision, floating-point underflow and overflow, drastically increasing computation time and program hang-ups, and instability due to numerical cancellation have all been reported. It is therefore recommended that existing statistical packages are cross-checked, and the present paper proposes a numerical algorithm precisely for this purpose. To the best of our knowledge, the proposed method is the first method that can compute the noncentrality parameter of the noncentral-F distribution with guaranteed accuracy over a wide parameter range that spans the range relevant for practical applications. Although the proposed method is limited to cases where the the degree of freedom of the denominator of the F test statistic is even, it does not affect its usefulness significantly: All of those algorithmic failures and inaccuracies that we can still reproduce today could have been prevented by simply cross-checking against the proposed method. Two numerical examples are presented where the intermediate computations went wrong silently, but the final result of the computations seemed nevertheless plausible, and eventually erroneous results were published. Cross-checking against the proposed method would have caught the numerical errors in both cases. The source code of the algorithm is available on GitHub, together with self-contained command-line executables. These executables can read the data to be cross-checked from plain text files, making it easy to cross-check any statistical software in an automated fashion.


F. Domes, T. Montanher, H. Schichl, A. Neumaier: Rigorous global filtering methods with interval unions, to appear in: Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy, etc. Methods and Their Applications (O. Kosheleva, et al., eds.) (2018).
This paper considers rigorous filtering methods for constraint satisfaction problems using interval union arithmetic. Interval unions are finite sets of closed and disjoint intervals that generalize the interval arithmetic. They allow a natural representation of the solution set of interval powers, trigonometric functions and the division by intervals containing zero. We combine the interval union arithmetic with the forward-backward constraint propagation procedure on directed acyclic graphs (DAGs) and extend the interval Newton operator to the interval union framework. Numerical experiments show that the interval union approach reduces the search space even when other rigorous state-of-the-art methods fail. Since the methods presented in this paper may produce a large number of boxes at each iteration, we also address this problem by using suitable gap-filling strategies. Using constraint satisfaction problems from the COCONUT test set the usefulness of the new methods is shown.


Tiago Montanher, Ferenc Domes, Hermann Schichl, Arnold Neumaier, Using interval unions to solve linear systems of equations with uncertainty, BIT Numerical Mathematics (2017) 3 pp. 901-926, DOI: 10.1007/s10543-017-0657-x online publication
An interval union is a finite set of closed and disjoint intervals. In this paper we introduce the interval union Gauss-Seidel procedure to rigorously enclose the solution set of linear systems with uncertainties given by intervals or interval unions. We also present the interval union midpoint and Gauss-Jordan preconditioners. The Gauss-Jordan preconditioner is used in a mixed strategy to improve the quality and efficiency of the algorithm. Numerical experiments on interval linear systems generated at random show the capabilities of our approach.


Hermann Schichl, Ferenc Domes, Tiago Montanher, Kevin Kofler, Interval unions, BIT Numerical Mathematics (2016) 2 pp. 531-556, DOI: 10.1007/s10543-016-0632-y online publication
This paper introduces interval union arithmetic, a new concept which extends the traditional interval arithmetic. Interval unions allow to manipulate sets of disjoint intervals and provide a natural way to represent the extended interval division. Considering interval unions lead to simplifications of the interval Newton method as well as of other algorithms for solving interval linear systems. This paper does not aim at describing the complete theory of interval union analysis, but rather at giving basic definitions and some fundamental properties, as well as showing theoretical and practical usefulness of interval unions in a few selected areas.


W. Stöllinger, H. Schichl, J. Kirnbauer, H. Bruckner, E. Bölcskey, High strength wood fibre construction concrete based on UHPC technology, in Innovative concrete techology in practice, proceedings of the 11th Central European Congress on Concrete Engineering in Hainburg, October 2015, pages 327-331.
In this paper we present structural wood fibre concrete mixtures based on UHPC technology with densities between 1360 and 2000 kgm3 that have compressive strengths between 35 and 90 MPa and bending tensile strengths between 7 and 14 MPa. Those mixtures are based on UHPC matrices with regular to relatively low cement content and require no or almost no compaction. The wood fiber content varies between 46 V-% and 14 V-% and 20 M-% and 5 M-% and consists of coniferous wood that had been made hydrophobic by chemical additives. The UHPC matrices were optimized using mathematical methods. Mathematical optimization was used to compute the mixture components.

H. Schichl, M. Sellmann, Predisaster Preparation of Transportation Networks, AAAI 2015, 709-715.
We develop a new approach for a pre-disaster planning problem which consists in computing an optimal investment plan to strengthen a transportation network, given that a future disaster probabilistically destroys links in the network. We show how the problem can be formulated as a non-linear integer program and devise an AI algorithm to solve it. In particular, we introduce a new type of extreme resource constraint and develop a practically efficient propagation algorithm for it. Experiments show several orders of magnitude improvements over existing approaches, allowing us to close an existing real-world benchmark and to solve to optimality other, more challenging benchmarks.
Roland Steinbauer, Evelyn Süss-Stepancik and Hermann Schichl, Einführung in das mathematische Arbeiten &emdash; der Passage-Point an der Universität Wien (German; Introduction into mathematical methodology: the passage point at Vienna University), pp 410-424 in Mathematische Vor- und BrĂźckenkurse edited by Bausch, I et al (Springer Spektrum, 2014).
pdf file
Wir beschreiben die Studieneingangsphase der Mathematikstudien an der Universität Wien und präsentieren erste Ergebnisse einer begleitenden empirischen Studie aus dem Wintersemester 2010/11.


H. Schichl, M. C. Markót, and A. Neumaier, Exclusion Regions for Optimization Problems, Journal of Global Optimization 59(2-3), 2014, 569-595, pdf file (244K), DOI :10.1007/s10898-013-0137-z
Branch and bound methods for finding all solutions of a global optimization problem in a box frequently have the difficulty that subboxes containing no solution cannot be easily eliminated if they are close to the global minimum. This has the effect that near each global minimum, and in the process of solving the problem also near the currently best found local minimum, many small boxes are created by repeated splitting, whose processing often dominates the total work spent on the global search.

This paper discusses the reasons for the occurrence of this so-called cluster effect, and how to reduce the cluster effect by defining exclusion regions around each local minimum found, that are guaranteed to contain no other local minimum and hence can safely be discarded. In addition, we will introduce a method for verifying the existence of a feasible point close to an approximate local minimum.

These exclusion regions are constructed using uniqueness tests based on a second order Krawczyk operator and make use of first, second and third order information on the objective and constraint functions.


M. C. Markót and H. Schichl, Bound Constrained Interval Global Optimization in the COCONUT Environment, Journal of Global Optimization 40(4), 2014, pdf file (244K), DOI: 10.1007/s10898-013-0139-x
GOP_ex is a bound constrained general purpose interval GO algorithm originated back to the GOP_ex sample program of the C-XSC Toolbox for Verified Computing, further improved by M. C. Markót since 1997 and used successfully in various scientific studies. The COCONUT Environment developed under the leadership of H. Schichl, is a modular open-source environment for global optimization problems, which can be expanded by commercial and open-source solver components (inference engines). Since the GOP_ex code has the main disadvantage that it is hard to extend and hard to interface with other interval related methods for global optimization, it was a straightforward idea to implement the GOP_ex algorithm as a new solver in the COCONUT framework. After we had implemented the new coco_gop_ex solver, we developed some extensions of it with COCONUT tools: the possibility to switch from the less efficient forward gradient evaluation mode to backward mode; a new way to compute the gradient, the Hessian, and the third order derivative of the objective by evaluating the function, gradient, and Hessian of the derivative expressions appearing as subexpressions in the automatically generated Karush-John conditions. The original first order centered form improvements for the range of the objective are now extensible with second and third order centered forms (resulting in substantially better range enclosures in many cases). Finally, we extended the algorithm with the possibility of calling local solvers, calling constraint propagation in various ways, and using exclusion box techniques (to reduce the cluster effect). The resulting algorithm variants were compared to each other and to the original GOP_ex implementation on about 200 bound constrained test problems; we concluded that the improved COCONUT-based algorithm far outperforms its predecessor. Another test run shows that our implementation is competitive with the BARON software, being even faster for many problem instances.


F. Domes, M. Fuchs, and H. Schichl, The Optimization Test Environment, Optimization and Engineering (2013), DOI 10.1007/s11081-013-9234-6.
The Optimization Test Environment is an interface to efficiently test different optimization solvers. It is designed as a tool for both developers of solver software and practitioners who just look for the best solver for their specific problem class. It enables users to:

The Optimization Test Environment is free to use for research purposes.


H. Schichl, A. Neumaier, M.C. Markot and F. Domes, On solving mixed-integer constraint satisfaction problems with unbounded variables, pp. 216-233 in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 7874 (2013).
Many mixed-integer constraint satisfaction problems and global optimization problems contain some variables with unbounded domains. Their solution by branch and bound methods to global optimality poses special challenges as the search region is infinitely extended. Many usually strong bounding methods lose their efficiency or fail altogether when infinite domains are involved. Most implemented branch and bound solvers add artificial bounds to make the problem bounded, or require the user to add these. However, if these bounds are too small, they may exclude a solution, while when they are too large, the search in the resulting huge but bounded region may be very inefficient. Moreover, if the global solver must provide a rigorous guarantee (as for the use in computer-assisted proofs), such articial bounds are not permitted without justication by proof. We developed methods based on compactication and projective geometry as well as asymptotic analysis to cope with the unboundedness in a rigorous manner. Based on projective geometry we implemented two different versions of the basic idea, namely (i) projective constraint propagation, and (ii) projective transformation of the variables, in the rigorous global solvers COCONUT and GloptLab. Numerical tests demonstrate the capability of the new technique, combined with standard pruning methods, to rigorously solve unbounded global problems. In addition, we present a generalization of projective transformation based on asymptotic analysis. Compactification and projective transformation, as well as asymptotic analysis, are useless in discrete situations. But they can very well be applied to compute bounded relaxations, and we present methods for doing that in an efficient manner.

H. Schichl and M. C. Markót, Algorithmic differentiation techniques for global optimization in the COCONUT environment, Optimization Methods and Software 27(2), 359-372, 2012
pdf file (182K),
We describe algorithmic differentiation as it can be used in algorithms for global optimization. We focus on the algorithmic differentiation methods implemented in the COCONUT Environment for global nonlinear optimization.

The COCONUT Environment represents each factorable optimization problem as a directed acyclic graph (DAG). Various inference modules implemented in this software environment can serve as building blocks for solution algorithms. Many of them use techniques based on various forms of algorithmic differentiation for computing approximations or enclosures of functions or their derivatives.

The algorithmic differentiation in the COCONUT Environment does not only provide point evaluations but also range enclosures of derivatives up to order 3, as well as slopes up to second order. Care is taken to ensure that rounding errors are treated correctly. The ranges of the enclosures can be tightened by combining the evaluation routines with constraint propagation. Advantages and pitfalls of this method are also outlined.


P. Schodl, A. Neumaier, K. Kofler, F. Domes, and H. Schichl, Towards a Self-reflective, Context-aware Semantic Representation of Mathematical Specifications Chapter 2 in Algebraic Modeling Systems - Modeling and Solving Real World Optimization Problems, (J. Kallrath (Ed.)), 2012.
We discuss a framework for the representation and processing of mathematics developed within and for the MOSMATH project. The MOSMATH project aims to create a software system that is able to translate optimization problems from an almost natural language to the algebraic modeling language AMPL. As part of a greater vision (the FMathL project), this framework is designed both to serve the optimization-oriented MOSMATH project, and to provide a basis for the much more general FMathL project.
We introduce the semantic memory, a data structure to represent semantic information, a type system to define and assign types to data, and the semantic virtual machine (SVM), a low level, Turing-complete programming system that processes data represented in the semantic memory.
Two features that set our approach apart from other frameworks are the possibility to reflect every major part of the system within the system itself, and the emphasis on the context-awareness of mathematics.
Arguments are given why this framework appears to be well suited for the representation and processing of arbitrary mathematics. It is discussed which mathematical content the framework is currently able to represent and interface.


M. C. Markót and H. Schichl, Comparison and automated selection of local optimization solvers for interval global optimization methods, SIAM J. Optim. 21, 1371-1391, 2011.
pdf file (244K),
We compare six state-of-the-art local optimization solvers with focus on their efficiency when invoked within an interval-based global optimization algorithm. For comparison purposes we design three special performance indicators: a solution check indicator (measuring whether the local minimizers found are good candidates for near-optimal verified feasible points), a function value indicator (measuring the contribution to the progress of the global search), and the running time indicator (estimating the computational cost of the local search within the global search). The solvers are compared on the COCONUT Environment test set consisting of 1307 problems. Our main target is to predict the behavior of the solvers in terms of the three performance indicators on a new problem. For this we introduce a $k$-nearest neighbor method applied over a feature space consisting of several categorical and numerical features of the optimization problems. The quality and robustness of the prediction is demonstrated by various quality measurements with detailed comparative tests. In particular, we found that on the test set we are able to pick a `best' solver in 66--89\% of the cases and avoid picking all `useless' solvers in 95--99\% of the cases (when a useful alternative exists). The resulting automated solver selection method is implemented as an inference engine of the COCONUT Environment.


M. Kieffer, M. C. Markót, H. Schichl, and E. Walter, Verified global optimization for estimating the parameters of nonlinear models, Chapter 7 in Modeling, Design, and Simulation of Systems with Uncertainties, Volume 3 of the Springer Series Mathematical Engineering (Rauh, Andreas; Auer, Ekaterina (Eds.)), 2011.
pdf file (290K),
Nonlinear parameter estimation is usually achieved via the minimization of some possibly non-convex cost function. Interval analysis provides tools for the guaranteed characterization of the set of all global minimizers of such a cost function when a closed-form expression for the output of the model is available or when this output is obtained via the numerical solution of a set of ordinary differential equations. However, cost functions involved in parameter estimation are usually challenging for interval techniques, if only because of multi-occurrences of the parameters in the formal expression of the cost. This paper addresses parameter estimation via the verified global optimization of quadratic cost functions. It introduces tools instrumental for the minimization of generic cost functions. When a closedform expression of the output of the parametric model is available, significant improvements may be obtained by a new box exclusion test and by careful manipulations of the quadratic cost function. When the model is described by ODEs, some of the techniques available in the previous case may still be employed, provided that sensitivity of the model output with respect to the parameters are available.


A. Viehweider, H. Schichl, D. Burnier de Castro, S. Henein, D. Schwabeneder, Smart robust voltage control for distribution networks using interval arithmetic and state machine concepts, in Proceedings IEEE PES Conference on Innovative Smart Grid Technologies Europe, IEEE PES, Chalmers, 2010, Paper-Nr. 2045882.
R. Fourer, C. Maheshwari, A. Neumaier, D. Orban and H. Schichl, Convexity and Concavity Detection in Computational Graphs, INFORMS Journal on Computing 22,1, 2010, 26-43, DOI:10.1287/ijoc.1090.0321
pdf file,
We examine symbolic tools associated with two modeling systems for mathematical programming, which can be used to automatically detect the presence or absence of convexity and concavity in the objective and constraint functions, as well as convexity of the feasible set in some cases. The coconut solver system [Schichl, H. 2004a. COCONUT: COntinuous CONstraints - Updating the technology.] focuses on nonlinear global continuous optimization and possesses its own modeling language and data structures. The Dr. ampl meta-solver [Fourer, R., D. Orban. 2007. The DrAMPL meta solver for optimization. Technical Report G-2007-10, GERAD, Montréal] aims to analyze nonlinear differentiable optimization models and hooks into the ampl Solver Library [Gay, D. M. 2002. Hooking your solver to AMPL.]. Our symbolic convexity analysis may be supplemented, when it returns inconclusive results, with a numerical phase that may detect nonconvexity. We report numerical results using these tools on sets of test problems for both global and local optimization.


Hermann Schichl and Roland Steinbauer, Einführung in das mathematische Arbeiten: Ein Projekt zur Gestaltung der Studieneingangsphase an der Universität Wien (German; Introduction into mathematical methodology: A new strategy for the first semester), Mitteilungen der DMV (Notices of the German Mathematical Society), 17(4), 244--246, (2009).


Vu Xuan-Ha, H. Schichl, and D. Sam-Haroud, Interval Propagation and Search on Directed Acyclic Graphs for Numerical Constraint Solving, Journal of Global Optimization, 45 (4), 499-531 (2009).
pdf file (725K),
The fundamentals of interval analysis on directed acyclic graphs (DAGs) for global optimization and constraint propagation have recently been proposed in Schichl and Neumaier (J. Global Optim. 33, 541?562, 2005). For representing numerical problems, the authors use DAGs whose nodes are subexpressions and whose directed edges are computational flows. Compared to tree-based representations [Benhamou et al. Proceedings of the International Conference on Logic Programming (ICLP?99), pp. 230-244. Las Cruces, USA (1999)], DAGs offer the essential advantage of more accurately handling the influence of subexpressions shared by several constraints on the overall system during propagation. In this paper we show how interval constraint propagation and search on DAGs can be made practical and efficient by: (1) flexibly choosing the nodes on which propagations must be performed, and (2) working with partial subgraphs of the initial DAG rather than with the entire graph. We propose a new interval constraint propagation technique which exploits the influence of subexpressions on all the constraints together rather than on individual constraints. We then show how the new propagation technique can be integrated into branch-and-prune search to solve numerical constraint satisfaction problems. This algorithm is able to outperform its obvious contenders, as shown by the experiments.


H. Schichl and A. Neumaier, Transposition theorems and qualification-free optimality conditions, SIAM J. Optimization, 17, 1035-1055 (2006).
ps.gz file (166K), pdf file (197K)
downloading/printing problems?
New theorems of the alternative for polynomial constraints (based on the Positivstellensatz from real algebraic geometry) and for linear constraints (generalizing the transposition theorems of Motzkin and Tucker) are proved. Based on these, two Karush-John optimality conditions -- holding without any constraint qualification -- are proved for single- or multi-objective constrained optimization problems. The first condition applies to polynomial optimization problems only, and gives for the first time necessary and sufficient global optimality conditions for polynomial problems. The second condition applies to smooth local optimization problems and strengthens known local conditions. If some linear or concave constraints are present, the new version reduces the number of constraints for which a constraint qualification is needed to get the Kuhn-Tucker conditions.


M. Kunzinger, H. Schichl, R. Steinbauer, and J. A. Vickers, Global Gronwall Estimates for Integral Curves on Riemannian Manifolds, Rev. Mat. Complut. 19/1 (2006), 133-137,
ps.gz file (167K), pdf file (152K)
downloading/printing problems?
We prove several Gronwall-type estimates for the distance of integral curves of smooth vector fields on a Riemannian manifold.


H. Schichl and A. Neumaier, Interval Analysis on Directed Acyclic Graphs for Global Optimization, Journal of Global Optimization 33/4 (2005), 541-562
(online) at http://dx.doi.org/10.1007/s10898-005-0937-x
compressed ps file (67K), pdf file (221K), Slides, Part 1, Slides, Part 2
downloading/printing problems?
A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation.
Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation.
The implementation is based on earlier work by Kolev on optimal slopes and by Bliek on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly.
Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian.
The linear underestimators can be found either by slope computations, or by recursive backward underestimation.
For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian).


X.-H. Vu, H. Schichl and D. Sam-Haroud, Using Directed Acyclic Graphs to Coordinate Propagation and Search for Numerical Constraint Satisfaction Problems, In Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), pages 72-81, Florida, USA, November 2004.
pdf file (527K)
ps.gz file (566K)
downloading/printing problems?
Given the fundamentals of interval analysis on DAGs for global optimization and constraint propagation, we show in this paper how constraint propagation on DAGs can be made efficient and practical by: (i) working on partial DAG representations; and (ii) enabling the flexible choice of the interval inclusion functions during propagation. We then propose a new simple algorithm which coordinates constraint propagation and exhaustive search for solving numerical constraint satisfaction problems. The experiments carried out on different problems show that the new approach outperforms previously available propagation techniques by an order of magnitude or more in speed, while being roughly the same quality w.r.t. enclosure properties.


H. Schichl and A. Neumaier, Exclusion regions for systems of equations, SIAM J. Numer. Anal. 42 (2004), 383--408.
pdf file (826K)
downloading/printing problems?
Branch and bound methods for finding all zeros of a nonlinear system of equations in a box frequently have the difficulty that subboxes containing no solution cannot be easily eliminated if there is a nearby zero outside the box. This has the effect that near each zero, many small boxes are created by repeated splitting, whose processing may dominate the total work spent on the global search.
This paper discusses the reasons for the occurrence of this so-called cluster effect, and how to reduce the cluster effect by defining exclusion regions around each zero found, that are guaranteed to contain no other zero and hence can safely be discarded.
Such exclusion regions are traditionally constructed using uniqueness tests based on the Krawczyk operator or the Kantorovich theorem. These results are reviewed; moreover, refinements are proved that significantly enlarge the size of the exclusion region. Existence and uniqueness tests are also given.


H. Schichl, Global Optimization in the COCONUT project, in Proceedings of the Dagstuhl Seminar "Numerical Software with Result Verification", Springer Lecture Notes in Computer Science 2991, Springer, Berlin, 2004.
ps.gz file (909K), pdf file (381K)
downloading/printing problems?
In this article, a solver platform for global optimization is presented, as it is developed in the COCONUT project. After a short introduction, a short description is given of the basic algorithmic concept and of all relevant components, the strategy engine, inferenence engines, and the remaining modules. A compact description of the search graph and its nodes and of the internal model representation using directed acyclic graphs (DAGs) completes the presentation.


H. Schichl, Models and the History of Modeling, Chapter 2, pp. 25-36 in: Modeling Languages in Mathematical Optimization (J. Kallrath, ed.), Kluwer, Boston 2004.
ps.gz file (213K), pdf file (207K), downloading/printing problems?
After a very fast tour through 30,000 years of modeling history, I will describe the basic ingredients to models in general, and to mathematical models in particular.


H. Schichl, Theoretical Concepts and Design of Modeling Languages, Chapter 4, pp. 45-62 in: Modeling Languages in Mathematical Optimization (J. Kallrath, ed.), Kluwer, Boston 2004.
ps.gz file (222K), pdf file (222K), downloading/printing problems?
Here, I will present the basic design features of modeling languages, turning our attention to algebraic modeling languages. Later I will introduce an important class of optimization problems --- global optimization, and illustrate the difficulties in constructing models for such problems.


H. Schichl and A. Neumaier, The NOP-2 Modeling Language, Chapter 15, pp. 279-292 in: Modeling Languages in Mathematical Optimization (J. Kallrath, ed.), Kluwer, Boston 2004.
ps.gz file (192K), pdf file (174K), downloading/printing problems?
We present a short overview over the modeling language NOP-2 for specifying general optimization problems, including constrained local or global nonlinear programs and constrained single and multistage stochastic programs. The proposed language is specifically designed to represent the internal (separable and repetitive) structure of the problem.


H. Schichl, A. Neumaier and S. Dallwig, The NOP-2 modeling language, Ann. Oper. Research 104 (2001), 281-312.
dvi.gz file (32K), ps.gz file (97K), pdf file (179K), downloading/printing problems?
An enhanced version NOP-2 of the NOP language for specifying global optimization problems is described. Because of its additional features, NOP-2 is comparable to other modeling languages like AMPL and GAMS, and allows the user to define a wide range of problems arising in real life applications such as global constrained (and even stochastic) optimization programs.
NOP-2 permits named variables, parameters, indexing, loops, relational operators, extensive set operations, matrices and tensors, and parameter arithmetic.
The main advantage that makes NOP-2 look and feel considerably different from other modeling languages is the display of the internal analytic structure of the problem. It is fully flexible for interfacing with solvers requiring special features such as automatic differentiation or interval arithmetic.

A.Cap and H. Schichl, Parabolic Geometries and Canonical Cartan Connections, Hokkaido Math. J., 29, 3 (2000), 453-505
ps.gz file (47K), pdf file (74K), downloading/printing problems?
Also available as ESI preprint 450.
Let $G$ be a (real or complex) semisimple Lie group, whose Lie algebra $\mathfrak{g}$ is endowed with a so called $|k|$--grading, i.e. a grading of the form $\mathfrak{g}=\mathfrak{g}_{-k}\oplus\dots\oplus \mathfrak{g}_k$, such that no simple factor of $G$ is of type $A_1$. Let $P$ be the subgroup corresponding to the subalgebra $\mathfrak{p}= \mathfrak{g}_0\oplus\dots\oplus\mathfrak{g}_k$. The aim of this paper is to clarify the geometrical meaning of Cartan connections corresponding to the pair $(G,P)$ and to study basic properties of these geometric structures.
Let $G_0$ be the (reductive) subgroup of $P$ corresponding to the subalgebra $\mathfrak{g}_0$. A principal $P$--bundle $E$ over a smooth manifold $M$ endowed with a (suitably normalized) Cartan connection $\omega\in\Omega^1(E,\mathfrak{g})$ automatically gives rise to a filtration of the tangent bundle $TM$ of $M$ and to a reduction to the structure group $G_0$ of the associated graded vector bundle to the filtered vector bundle $TM$. We prove that in almost all cases the principal $P$ bundle together with the Cartan connection is already uniquely determined by this underlying structure (which can be easily understood geometrically), while in the remaining cases one has to make an additional choice (which again can be easily interpreted geometrically) to determine the bundle and the Cartan connection.


A. Neumaier, S. Dallwig, W. Huyer and H. Schichl, New techniques for the construction of residue potentials for protein folding, pp. 212-224 in: Algorithms for Macromolecular Modelling (P. Deuflhard et al., eds.), Lecture Notes Comput. Sci. Eng. 4, Springer, Berlin 1999.
download

P.W. Michor and H. Schichl, No slices on the space of generalized connections, Acta Math. Univ. Comenianiae, 66, 2 (1997), 221-228
ps.gz file (68K), downloading/printing problems?
Also available as ESI preprint 453.
On a fiber bundle without structure group the action of the gauge group (the group of all fiber respecting diffeomorphisms) on the space of (generalized) connections is shown to admit no slices.


S. Dallwig, A. Neumaier and H. Schichl, GLOPT - A Program for Constrained Global Optimization, pp. 19-36 in: I. Bomze et al., eds., Developments in Global Optimization, Kluwer, Dordrecht 1997.
ps.gz file (100K), pdf file (183K), downloading/printing problems?
GLOPT is a Fortran77 program for global minimization of a block-separable objective function subject to bound constraints and block-separable constraints. It finds a nearly globally optimal point that is near a true local minimizer. Unless there are several local minimizers that are nearly global, we thus find a good approximation to the global minimizer.
GLOPT uses a branch and bound technique to split the problem recursively into subproblems that are either eliminated or reduced in their size. This is done by an extensive use of the block separable structure of the optimization problem.
In this paper we discuss a new reduction technique for boxes and new ways for generating feasible points of constrained nonlinear programs. These are implemented as the first stage of our GLOPT project. The current implementation of GLOPT uses neither derivatives nor simultaneous information about several constraints. Numerical results are already encouraging. Work on an extension using curvature information and quadratic programming techniques is in progress.


A.Cap and H. Schichl, Characteristic Classes for A-bundles, "Proc. of the Winter School on Geometry and Physics, Srni 1994" Supp. ai Rend. Circolo. Math. Palermo, II, 39, (1996), 57-71
ps.gz file (102K), pdf file (205K), downloading/printing problems?
We consider locally trivial bundles over smooth manifolds, whose fibers are finitely generated projective modules over a convenient algebra $A$. For such a bundle $E\to X$ and a bounded reduced cyclic cocycle $c$ on $A$ we construct a sequence $\chi_c^k(E)$ of de--Rham cohomology classes on $X$, which are an analog of the classical Chern character. We show that these classes depend only on the cohomology class of $c$ and behave natural under various constructions.


A.Cap and H. Schichl and J. Vanzura, On Twisted Tensor Products of Algebras, Commun. Algebra, 23, 12 (1995), 4701-4735
ps.gz file (47K), pdf file (74K), downloading/printing problems?
Also available as ESI preprint 163.
The problems considered in this paper are motivated by non-commutative geometry. Starting from two unital algebras $A$ and $B$ over a commutative ring $\mathbb{K}$ we describe all triples $(C,i_A,i_B)$, where $C$ is a unital algebra and $i_A$ and $i_B$ are inclusions of $A$ and $B$ into $C$ such that the canonical linear map $(i_A,i_B):A\otimes B\to C$ is a linear isomorphism. We discuss possibilities to construct differential forms and modules over $C$ from differential forms and modules over $A$ and $B$, and give a description of deformations of such structures using cohomological methods.


A.Cap and P.W. Michor and H. Schichl, A quantum group like structure on non commutative 2-tori, Letters in Math. Phys., 28, (1993), 251-255
ps.gz file (39K), pdf file (89K), downloading/printing problems?
Also available as ESI preprint 6.
In this paper we show that in the case of non commutative two tori one gets in a natural way simple structures which have analogous formal properties as Hopf algebra structures but with a deformed multiplication on the tensor product.


Technical Reports



H. Schichl, VGTL (Vienna Graph Template Library) Version 1.4, Reference Manual, Technical Report, January 2013, 384 pages
pdf file (3400K),
This technical report contains the complete commented class reference of the Vienna Graph Template Library.


H. Schichl, VDBL (Vienna Database Library) Version 1.2, Reference Manual, Technical Report, February 2013, 229 pages,
pdf file (2364K),
This technical report contains the complete commented class reference of the Vienna Graph Template Library.


H. Schichl, The COCONUT API Version 4.00, Reference Manual, Technical Report, July 2013, 2307 pages,
pdf file (22200K),
This technical report contains the complete class reference of the COCONUT API.


C. Bliek, H. Schichl, Specification of modules interface, Internal representation, and modules API, Technical Report, Deliverable D6 of the COCONUT project (August 2002), 37 pages,
pdf file (226K), downloading/printing problems?
This technical report contains the interface definitions between the various module classes, the evaluators, and the base classes for modules in COCONUT API Version 1.


H. Schichl, VGTL (Vienna Graph Template Library) Version 1.0, Reference Manual, Technical Report, Appendix to "Upgraded State of the Art Techniques implemented as Modules", Deliverable D13 of the COCONUT project (July 2003), Version 1.1 (October 2003), 323 pages,
pdf file (3114K), html, downloading/printing problems?
This technical report contains the complete commented class reference of the Vienna Graph Template Library.


H. Schichl, VDBL (Vienna Database Library) Version 1.0, Reference Manual, Technical Report, Appendix to "Upgraded State of the Art Techniques implemented as Modules", Deliverable D13 of the COCONUT project (July 2003), 163 pages,
pdf file (1565K), html, downloading/printing problems?
This technical report contains the complete commented class reference of the Vienna Graph Template Library.


H. Schichl, The COCONUT API Version 2.32, Reference Manual, Technical Report, [Version 2.13 (July 2003)], Appendix to "Specification of new and improved representations", Deliverable D5 v2 of the COCONUT project (November 2003), 510 pages,
pdf file (5981K), html, downloading/printing problems?
This technical report contains the complete class reference of the COCONUT API.


C. Maheshwari, A. Neumaier, and H. Schichl, Convexity and concavity detection, Technical Report, in "New Techniques as Modules", Deliverable D12 of the COCONUT project (July 2003), pages 61-67,
ps file (422K), downloading/printing problems?
This technical report contains the mathematical background of some techniques for automatic convexity detection in expressions.


H. Schichl, An introduction to the Vienna Database Library, Technical Report, in "Upgraded State of the Art Techniques implemented as Modules", Deliverable D13 of the COCONUT project (July 2003), pages 29-31,
ps file (237K), downloading/printing problems?
This technical report contains a short introduction to the VDBL (Vienna Database Library), one of the basic libraries of the COCONUT API.


H. Schichl, Changes and new features in API 2.x,