Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization

Oleg Shcherbina ()
Additional contact information
Oleg Shcherbina: University of Vienna

A chapter in Operations Research Proceedings 2006, 2007, pp 155-160 from Springer

Abstract: Abstract Solving discrete optimization problems (DOP) can be a rather hard task. Many real DOPs contain a huge number of variables and/or constraints that make the models intractable for currently available solvers. There are few approaches for solving DOPs: tree search approaches (e.g., branch and bound), relaxation and decomposition methods. Large DOPs can be solved due to their special structure. Among decomposition approaches we can mention poorly known local decomposition algorithms using the special block matrix structure of constraints and half-forgotten nonserial dynamic programming algorithms which can exploit sparsity in the dependency graph of a DOP.

Keywords: Dependency Graph; Local Algorithm; Tree Decomposition; Interaction Graph; Discrete Optimization Problem (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-69995-8_26

Ordering information: This item can be ordered from
http://www.springer.com/9783540699958

DOI: 10.1007/978-3-540-69995-8_26

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().