Quantified Combinatorial Optimization

Thorsten Ederer (), Ulf Lorenz () and Thomas Opfer ()
Additional contact information
Thorsten Ederer: TU Darmstadt
Ulf Lorenz: TU Darmstadt
Thomas Opfer: TU Darmstadt

A chapter in Operations Research Proceedings 2013, 2014, pp 121-128 from Springer

Abstract: Abstract MIP and IP programming are state-of-the-art modeling techniques for computer-aided optimization. However, companies observe an increasing danger of disruptions that prevent them from acting as planned. One reason is input data being assumed as deterministic, but in reality, data is afflicted with uncertainties. Incorporating uncertainty in existing models, however, often pushes the complexity of problems that are in P or NP, to the complexity class PSPACE. Quantified integer linear programming (QIP) is a PSPACE-complete extension of the IP problem with variables being either existentially or universally quantified. With the help of QIPs, it is possible to model board-games like Gomoku as well as traditional combinatorial OR problems under uncertainty. In this paper, we present how to extend the model formulation of classical scheduling problems like the Job-Shop and Car-Sequencing problem by uncertain influences and give illustrating examples with solutions.

Keywords: Classical Scheduling Problems; Complexity Class PSPACE; Gomoku; Computer-aided Optimization; Uncertain Influence (search for similar items in EconPapers)
Date: 2014
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-319-07001-8_17

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

DOI: 10.1007/978-3-319-07001-8_17

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 ().