Advertisement
Published in:
2006 | OriginalPaper | Chapter
Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming
Authors : Claire Kenyon, Meinolf Sellmann
Published in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We address the following dilemma: When making decisions in real life, we often face the problem that, while we have time to contemplate about a problem, we are not entirely sure what the exact parameters of our problem will be. And, on the other hand, as soon as the real world is revealed to us, we need to act quickly and have no more time to rethink our actions extensively.
We suggest an approach that allows to trade uncertainty for time and marginal quality loss and discuss its applicability to combinatorial optimization problems that can be formulated as linear and integer linear programs. The core idea consists in solving a polynomial number of problems in the extensive time period before the day of operation, so that, as soon as complete information is available, a feasible near-optimal solution to the problem can be found in sublinear time.