article

Measuring the Quality of Approximate Solutions to Zero-One Programming Problems

Author:

Eitan ZemelAuthors Info & Claims

Mathematics of Operations Research, Volume 6, Issue 3

Pages 319 - 332

https://doi.org/10.1287/moor.6.3.319

Published: 01 August 1981 Publication History

Abstract

We point out the difficulties associated with measuring the quality of an approximate heuristic solution by “Percentage-Error” as is customary. We define a set of properties that are to be expected from a proper measure of solution quality and investigate the family of functions which satisfy those conditions. In particular, we show that for any class of 0--1 programming problems appropriate functions do exist and that they are uniquely defined up to monotone transformations. We conclude with several examples of linear functions which are suitable for certain classes of problems.

References

[1]

Cook, S. A. (1971). The Complexity of Theorem Proving Procedures. Proc. 3rd Annual ACM Symp. on the Theory of Computing, pp. 151-158.

Digital Library

Google Scholar

[2]

Cornuejols, G., Fisher, M. L. and Nemhauser, G. L. (1977). Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Sci. 23 789-810.

Google Scholar

[3]

Garey, M. R. and Johnson, D. S. (1976). Approximation Algorithm for Combinatorial Problems: An Annotated Bibliography. In Algorithm and Complexity: New Directions and Recent Results, S. F. Traub, ed. Academic Press, New York.

Google Scholar

[4]

Ibarra, O. H. and Kim, Ch. E. (1975). Fast Approximation Algorithms for the Knapsack and Sum of Subsets Problems. J. Assoc. Comput. Mach. 22 463-468.

Digital Library

Google Scholar

[5]

Johnson, D. S. (1974). Approximation Algorithms for Combinatorial Problems. J. Comput. System Sci. 9 256-278.

Digital Library

Google Scholar

[6]

Karp, R. M. (1975). On the Computational Complexity of Combinatorial Problems. Networks 5 45-68.

Digital Library

Google Scholar

[7]

Korte, B. (August 1977). Approximation Algorithms for Discrete Optimization Problems. Presented at Discrete Optimization 77, Vancouver, British Columbia.

Google Scholar

[8]

Sahni, S. and Gonzales, T. (1976). P Complete Approximation Problems. J. Assoc. Comput. Mach. 23 555-565.

Digital Library

Google Scholar

Cited By

View all

Silva AValente JSchaller J(2022)Metaheuristics for the permutation flowshop problem with a weighted quadratic tardiness objectiveComputers and Operations Research10.1016/j.cor.2021.105691140:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105691
usti APunnen A(2017)Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysisOperations Research Letters10.1016/j.orl.2017.03.00445:3(232-237)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.orl.2017.03.004
ăźUstić ASokol VPunnen ABhattacharya B(2017)The bilinear assignment problemMathematical Programming: Series A and B10.1007/s10107-017-1111-1166:1-2(185-205)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10107-017-1111-1
Show More Cited By

Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems

This paper is concerned with a new linearization strategy for a class of zero-one mixed integer programming problems that contains quadratic cross-product terms between continuous and binary variables, and between the binary variables themselves. This ...
An Approach to Zero-One Integer Programming

By starting with an all-integer zero-one linear programming problem, it is possible to develop a modified, possibly linear, programming problem that provides a characterization of the basis corresponding to a feasible zero-one solution to the integer ...
A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems

This paper is concerned with the solution of linearly constrained zero-one quadratic programming problems. Problems of this kind arise in numerous economic, location decision, and strategic planning situations, including capital budgeting, facility ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 6, Issue 3

August 1981

170 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 1981

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Silva AValente JSchaller J(2022)Metaheuristics for the permutation flowshop problem with a weighted quadratic tardiness objectiveComputers and Operations Research10.1016/j.cor.2021.105691140:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105691
usti APunnen A(2017)Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysisOperations Research Letters10.1016/j.orl.2017.03.00445:3(232-237)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.orl.2017.03.004
ăźUstić ASokol VPunnen ABhattacharya B(2017)The bilinear assignment problemMathematical Programming: Series A and B10.1007/s10107-017-1111-1166:1-2(185-205)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10107-017-1111-1
Punnen ASripratak PKarapetyan D(2015)Average value of solutions for the bipartite boolean quadratic programs and rounding algorithmsTheoretical Computer Science10.1016/j.tcs.2014.11.008565:C(77-89)Online publication date: 2-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.008
Punnen ASripratak PKarapetyan D(2013)Domination analysis of algorithms for bipartite boolean quadratic programsProceedings of the 19th international conference on Fundamentals of Computation Theory10.1007/978-3-642-40164-0_26(271-282)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40164-0_26
Karapetyan DGutin G(2011)A new approach to population sizing for memetic algorithmsEvolutionary Computation10.1162/EVCO_a_0002619:3(345-371)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1162/EVCO_a_00026
Escoffier BPaschos V(2010)SurveyComputer Science Review10.1016/j.cosrev.2009.11.0014:1(19-40)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1016/j.cosrev.2009.11.001
Berend DSkiena STwitto Y(2008)Combinatorial dominance guarantees for problems with infeasible solutionsACM Transactions on Algorithms10.1145/1435375.14353835:1(1-29)Online publication date: 12-Dec-2008
https://dl.acm.org/doi/10.1145/1435375.1435383
Gutin GJensen TYeo A(2006)Domination analysis for minimum multiprocessor schedulingDiscrete Applied Mathematics10.1016/j.dam.2006.02.010154:18(2613-2619)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1016/j.dam.2006.02.010
Culus JDemange M(2006)Oriented coloringProceedings of the 32nd conference on Current Trends in Theory and Practice of Computer Science10.1007/11611257_20(226-236)Online publication date: 21-Jan-2006
https://dl.acm.org/doi/10.1007/11611257_20
Show More Cited By

Abstract

References

Cited By

Recommendations

Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems

An Approach to Zero-One Integer Programming

A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations