Ali Baharev
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ali Baharev has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
Arnold Neumaier
University of Vienna, Wien, Austria
4 shared publicationsEndre Rév
Budapest University of Technology and Economics, Budapest, Hungary
4 shared publicationsHermann Schichl
University of Vienna, Wien, Austria
4 shared publications- Arnold Neumaier
Fakultät für Mathematik, Universität Wien, Wien, Austria
2 shared publications Tobias Achterberg
Gurobi GmbH, Frankfurt am Main
2 shared publicationsFerenc Domes
Faculty of Mathematics, University of Vienna, Vienna, Austria
1 shared publication
Latest Publications
- Open Access
- 23 April 2021
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 26, 1-28
An Exact Method for the Minimum Feedback Arc Set Problem
A feedback arc set of a directed graph G is a subset of its arcs containing at least one arc of every cycle in G . Finding a feedback arc set of minimum cardinality is an NP-hard problem called the minimum feedback arc set problem . Numerically, the minimum set cover formulation of the minimum feedback arc set problem is appropriate as long as all simple cycles in G can be enumerated. Unfortunately, even those sparse graphs that are important for practical applications often have Ω (2 n ) simple cycles. Here we address precisely such situations: An exact method is proposed for sparse graphs that enumerates simple cycles in a lazy fashion and iteratively extends an incomplete cycle matrix. In all cases encountered so far, only a tractable number of cycles has to be enumerated until a minimum feedback arc set is found. The practical limits of the new method are evaluated on a test set containing computationally challenging sparse graphs, relevant for industrial applications. The 4,468 test graphs are of varying size and density and suitable for testing the scalability of exact algorithms over a wide range.
- 23 April 2021
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 26, 1-28
Open AccessAn Exact Method for the Minimum Feedback Arc Set Problem
A feedback arc set of a directed graph G is a subset of its arcs containing at least one arc of every cycle in G . Finding a feedback arc set of minimum cardinality is an NP-hard problem called the minimum feedback arc set problem . Numerically, the minimum set cover formulation of the minimum feedback arc set problem is appropriate as long as all simple cycles in G can be enumerated. Unfortunately, even those sparse graphs that are important for practical applications often have Ω (2 n ) simple cycles. Here we address precisely such situations: An exact method is proposed for sparse graphs that enumerates simple cycles in a lazy fashion and iteratively extends an incomplete cycle matrix. In all cases encountered so far, only a tractable number of cycles has to be enumerated until a minimum feedback arc set is found. The practical limits of the new method are evaluated on a test set containing computationally challenging sparse graphs, relevant for industrial applications. The 4,468 test graphs are of varying size and density and suitable for testing the scalability of exact algorithms over a wide range.
- Open Access
- 12 July 2019
- Published by Springer Nature in Journal of Global Optimization
- Vol. 75 (4) , 949-971
A manifold-based approach to sparse global constraint satisfaction problems
We consider square, sparse nonlinear systems of equations whose Jacobian is structurally nonsingular, with reasonable bound constraints on all variables. We propose an algorithm for finding good approximations to all well-separated solutions of such systems. We assume that the input system is ordered such that its Jacobian is in bordered block lower triangular form with small diagonal blocks and with small border width; this can be performed fully automatically with off-the-shelf decomposition methods. Five decades of numerical experience show that models of technical systems tend to decompose favorably in practice. Once the block decomposition is available, we reduce the task of solving the large nonlinear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The proposed method resolves this issue with the novel backsolve step. We study the effect of the decomposition on a sequence of challenging problems. Beyond a certain problem size, the computational effort of multistart (no decomposition) grows exponentially. In contrast, thanks to the decomposition, for the proposed method the computational effort grows only linearly with the problem size. It depends on the problem size and on the hyperparameter settings whether the decomposition and the more sophisticated algorithm pay off. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size hyperparameter improves the robustness of the proposed method.
- 12 July 2019
- Published by Springer Nature in Journal of Global Optimization
- Vol. 75 (4) , 949-971
Open AccessA manifold-based approach to sparse global constraint satisfaction problems
We consider square, sparse nonlinear systems of equations whose Jacobian is structurally nonsingular, with reasonable bound constraints on all variables. We propose an algorithm for finding good approximations to all well-separated solutions of such systems. We assume that the input system is ordered such that its Jacobian is in bordered block lower triangular form with small diagonal blocks and with small border width; this can be performed fully automatically with off-the-shelf decomposition methods. Five decades of numerical experience show that models of technical systems tend to decompose favorably in practice. Once the block decomposition is available, we reduce the task of solving the large nonlinear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The proposed method resolves this issue with the novel backsolve step. We study the effect of the decomposition on a sequence of challenging problems. Beyond a certain problem size, the computational effort of multistart (no decomposition) grows exponentially. In contrast, thanks to the decomposition, for the proposed method the computational effort grows only linearly with the problem size. It depends on the problem size and on the hyperparameter settings whether the decomposition and the more sophisticated algorithm pay off. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size hyperparameter improves the robustness of the proposed method.
- Open Access
- 4 July 2017
- Published by Linkoping University Electronic Press
- No. 132,p. 353-362
Failure Modes of Tearing and a Novel Robust Approach
Link?ping University Electronic Press Conference Proceedings
- 4 July 2017
- Published by Linkoping University Electronic Press
- No. 132,p. 353-362
Open AccessFailure Modes of Tearing and a Novel Robust Approach
Link?ping University Electronic Press Conference Proceedings
- Open Access
- 17 December 2016
- Published by Springer Nature in Numerical Algorithms
- Vol. 76 (1) , 163-189
A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations
- 17 December 2016
- Published by Springer Nature in Numerical Algorithms
- Vol. 76 (1) , 163-189
Open AccessA robust approach for finding all well-separated solutions of sparse systems of nonlinear equations
- Open Access
- 8 December 2016
- Published by Springer Nature in Computational Statistics
- Vol. 32 (2) , 763-779
Computing the noncentral-F distribution and the power of the F-test with guaranteed accuracy
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.
- 8 December 2016
- Published by Springer Nature in Computational Statistics
- Vol. 32 (2) , 763-779
Open AccessComputing the noncentral-F distribution and the power of the F-test with guaranteed accuracy
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.
- 22 November 2013
- Published by Wiley in AIChE Journal
- Vol. 60 (2) , 410-414
A globally convergent method for finding all steady‐state solutions of distillation columns
Significance: A globally convergent method is proposed that either returns all solutions to steady‐state models of distillation columns or proves their infeasibility. Initial estimates are not required. The method requires a specific but fairly general block‐sparsity pattern; in return, the computational efforts grow linearly with the number of stages in the column. The well‐known stage‐by‐stage (and the sequential modular) approach also reduces the task of solving high‐dimensional steady‐state models to that of solving a sequence of low‐dimensional ones. Unfortunately, these low‐dimensional systems are extremely sensitive to the initial estimates, so that solving them can be notoriously difficult or even impossible. The proposed algorithm overcomes these numerical difficulties by a new reparameterization technique. The successful solution of a numerically challenging reactive distillation column with seven steady‐states shows the robustness of the method. No published software known to the authors could compute all solutions to this difficult model without expert tuning. © 2013 American Institute of Chemical Engineers AIChE J 60: 410–414, 2014
- 22 November 2013
- Published by Wiley in AIChE Journal
- Vol. 60 (2) , 410-414
A globally convergent method for finding all steady‐state solutions of distillation columns
Significance: A globally convergent method is proposed that either returns all solutions to steady‐state models of distillation columns or proves their infeasibility. Initial estimates are not required. The method requires a specific but fairly general block‐sparsity pattern; in return, the computational efforts grow linearly with the number of stages in the column. The well‐known stage‐by‐stage (and the sequential modular) approach also reduces the task of solving high‐dimensional steady‐state models to that of solving a sequence of low‐dimensional ones. Unfortunately, these low‐dimensional systems are extremely sensitive to the initial estimates, so that solving them can be notoriously difficult or even impossible. The proposed algorithm overcomes these numerical difficulties by a new reparameterization technique. The successful solution of a numerically challenging reactive distillation column with seven steady‐states shows the robustness of the method. No published software known to the authors could compute all solutions to this difficult model without expert tuning. © 2013 American Institute of Chemical Engineers AIChE J 60: 410–414, 2014
- 19 November 2012
- Published by Linkoping University Electronic Press
- No. 076,p. 955-962
Chemical Process Modeling in Modelica
Link?ping University Electronic Press Conference Proceedings
- 19 November 2012
- Published by Linkoping University Electronic Press
- No. 076,p. 955-962
Chemical Process Modeling in Modelica
Link?ping University Electronic Press Conference Proceedings
- 5 May 2011
- Published by Wiley in AIChE Journal
- Vol. 57 (6) , 1485-1495
Computing multiple steady states in homogeneous azeotropic and ideal two‐product distillation
Multiple steady states are typically discovered by tracing a solution path, including turning points. A new technique is presented here that does not follow this approach. The original problem is solved directly, without tracing a solution path. The proposed branch‐and‐prune algorithm is guaranteed to find all solutions automatically. Core components of the framework are affine arithmetic, constraint propagation, and linear programming. The C++ implementation is available as an open‐source solver and has an interface to the AMPL® modeling environment. In certain difficult cases, only continuation methods have been reported to find the unstable solution automatically. The proposed method seems to be the first published alternative method in those cases. Although this article focuses mainly on distillation, the presented framework is fairly general and applicable to a wide variety of problems. Further, computational results are given to demonstrate this. © 2010 American Institute of Chemical Engineers AIChE J, 2011
- 5 May 2011
- Published by Wiley in AIChE Journal
- Vol. 57 (6) , 1485-1495
Computing multiple steady states in homogeneous azeotropic and ideal two‐product distillation
Multiple steady states are typically discovered by tracing a solution path, including turning points. A new technique is presented here that does not follow this approach. The original problem is solved directly, without tracing a solution path. The proposed branch‐and‐prune algorithm is guaranteed to find all solutions automatically. Core components of the framework are affine arithmetic, constraint propagation, and linear programming. The C++ implementation is available as an open‐source solver and has an interface to the AMPL® modeling environment. In certain difficult cases, only continuation methods have been reported to find the unstable solution automatically. The proposed method seems to be the first published alternative method in those cases. Although this article focuses mainly on distillation, the presented framework is fairly general and applicable to a wide variety of problems. Further, computational results are given to demonstrate this. © 2010 American Institute of Chemical Engineers AIChE J, 2011
- 18 May 2009
- Published by Wiley in AIChE Journal
- Vol. 55 (7) , 1695-1704
Computation of an extractive distillation column with affine arithmetic
The need of reliably solving systems of nonlinear equations often arises in the everyday practice of chemical engineering. In general, standard methods cannot provide theoretical guarantee for convergence to a solution, cannot reliably find multiple solutions, and cannot prove nonexistence of solutions. Interval methods provide tools to overcome these problems, thus achieving reliability. To the authors' best knowledge, computation of distillation columns with interval methods have not yet been considered in the literature. This article presents significant enhancements compared with a previously published interval method of the authors. The proposed branch‐and‐prune algorithm is guaranteed to converge, and is fairly general at the same time. If no solution exists then this information is provided by the method as a result. Power of the suggested method is demonstrated by solving, with guaranteed convergence, even the MESH equations of a 22 stage extractive distillation column with a ternary mixture. © 2009 American Institute of Chemical Engineers AIChE J, 2009
- 18 May 2009
- Published by Wiley in AIChE Journal
- Vol. 55 (7) , 1695-1704
Computation of an extractive distillation column with affine arithmetic
The need of reliably solving systems of nonlinear equations often arises in the everyday practice of chemical engineering. In general, standard methods cannot provide theoretical guarantee for convergence to a solution, cannot reliably find multiple solutions, and cannot prove nonexistence of solutions. Interval methods provide tools to overcome these problems, thus achieving reliability. To the authors' best knowledge, computation of distillation columns with interval methods have not yet been considered in the literature. This article presents significant enhancements compared with a previously published interval method of the authors. The proposed branch‐and‐prune algorithm is guaranteed to converge, and is fairly general at the same time. If no solution exists then this information is provided by the method as a result. Power of the suggested method is demonstrated by solving, with guaranteed convergence, even the MESH equations of a 22 stage extractive distillation column with a ternary mixture. © 2009 American Institute of Chemical Engineers AIChE J, 2009