Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1984
Abstract
We generalize the concept of duality, known for Linear Programming, to other optimization problems and introduce finite improvement algorithms as a class of algorithms which includes the simplex method. The concept of finite improvement is interesting because such algorithms can work on non-convex problems such as the Linear Complementarity problem. Our goal is to find the relationship between finite improvement, duality and optimization problems which can be considered tractable. The study of these concepts naturally includes consideration of complementary problems (CO-NP) and data-independent and data-dependent neighborhoods. We find that the class of optimization problems with duals is the same as NP ∩ CO-NP restricted to optimization problems. We also find that no NP-complete optimization problem can be solved by finite improvement unless NP = CO-NP. This result is an improvement over a similar one in [8]. Another interesting result is that any optimization problem with a sum-of-costs objective function which cannot be solved by finite improvement using small data-independent neighborhoods cannot be solved by the greedy method. We show that the Shortest Path problem is an example of such a problem. We show that Linear Programming can be solved by finite improvement on small data-independent neighborhoods and we discuss the well known transformation from Shortest Path to Linear Programming.
Keywords
Operations research, Mathematical optimization, Linear programming, Duality theory (Mathematics), Algorithms, Computational complexity, NP-complete problems
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 536
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Franco, J.; Solow, Daniel; and Emmons, Hamilton, "Duality, Finite Improvement and Efficiently Solved Problems" (1984). Research Reports from the Department of Operations. 164.
https://commons.case.edu/wsom-ops-reports/164