Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Critical and Maximum Independent Sets Revisited Read chapter Read first chapter

2019 | OriginalPaper | Chapter

A Dynamic Algorithm for Constructing the Dual Representation of a Polyhedral Cone

Authors : Sergey O. Semenov, Nikolai Yu. Zolotykh

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We propose a dynamic version of the double description method for generating the extreme rays of a polyhedral cone. The dynamic version of the algorithm supports online input of inequalities. Some modifications of the method were implemented and the results of computational experiments are presented. On a series of problems, our implementation of the algorithm showed higher performance results in comparison with the known analogues.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Splitting Method with Adaptive Step-Size
next chapter Comparison of Several Stochastic and Deterministic Derivative-Free Global Optimization Algorithms
Literature
1.
Amato, G., Scozzari, F., Zaffanella, E.: Efficient constraint/generator removal from double description of polyhedra. Electron. Notes Theor. Comput. Sci. 307, 3–15 (2014)MathSciNetCrossRef
2.
3.
4.
Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discret. Comput. Geom. 8(3), 295–313 (1992)MathSciNetCrossRef
5.
Bagnara, R., Hill, P.M., Zaffanella, E.: The Parma polyhedra library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Program. 72(1–2), 3–21 (2008)MathSciNetCrossRef
6.
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. (TOMS) 22(4), 469–483 (1996)MathSciNetCrossRef
7.
Bastrakov, S.I., Zolotykh, N.Y.: Elimination of inequalities from a facet description of a polyhedron. Trudy Inst. Mat. i Mekh. UrO RAN 21(3), 37–45 (2015). (in Russian)
8.
Bastrakov, S.I., Zolotykh, N.Y.: On the dynamic problem of computing generators of a polyhedral cone. Vestn. Yuzhno-Ural. Gos. Un-ta. Ser. Matem. Mekh. Fiz. 9(1), 5–12 (2017). (in Russian)MATH
9.
Bastrakov, S.I., Zolotykh, N.Y.: Fast method for verifying Chernikov rules in Fourier-Motzkin elimination. Comput. Math. Math. Phys. 55(1), 160–167 (2015)MathSciNetCrossRef
10.
Bremner, D., Fukuda, K., Marzetta, A.: Primal-dual methods for vertex and facet enumeration. Discret. Comput. Geom. 20(3), 333–357 (1998)MathSciNetCrossRef
11.
Chernikov, S.: Linear Inequalities. Nauka, Moscow (1968). (in Russian)MATH
12.
Chernikova, N.: Algorithm for finding a general formula for the non-negative solutions of system of linear inequalities. U.S.S.R. Comput. Math. Math. Phys. 5(2), 228–233 (1965)MathSciNetCrossRef
13.
Demenkov, M., Filimonov, N.: Polyhedral barrier regulator design using non-monotonic Lyapunov function. In: 2016 International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy’s Conference), pp. 1–3. IEEE (2016)
14.
15.
Horst, R., Pardalos, P.M., Van Thoai, N.: Introduction to Global Optimization. Springer, Dordrecht (2000)CrossRef
16.
Motzkin, T., Raiffa, H., Thompson, G., Thrall, R.: The double description method. In: Kuhn, H., Tucker, A.W. (eds.) Contributions to Theory of Games, vol. 2. Princeton University Press, Princeton (1953)
17.
Perry, J.: Exploring the dynamic Buchberger algorithm. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pp. 365–372. ACM (2017)
18.
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)MATH
19.
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2003)MATH
20.
Terzer, M., Stelling, J.: Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics 24(19), 2229–2235 (2008)CrossRef
21.
Ziegler, G.M.: Lectures on Polytopes, vol. 152. Springer, Heidelberg (2012)MATH
22.
Zolotykh, N.Y., Kubarev, V.K., Lyalin, S.S.: Double description method over the field of algebraic numbers. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki 28(2), 161–175 (2018). (in Russian)MathSciNetCrossRef
23.
Zolotykh, N.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. Math. Phys. 52(1), 146–156 (2012)MathSciNetCrossRef
Metadata
Title
A Dynamic Algorithm for Constructing the Dual Representation of a Polyhedral Cone
Authors
Sergey O. Semenov
Nikolai Yu. Zolotykh
Copyright Year
2019
Book
Mathematical Optimization Theory and Operations Research

Print ISBN: 978-3-030-22628-2

Electronic ISBN: 978-3-030-22629-9

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-22629-9_5

Premium Partner

    Image Credits