The Gap Function: Evaluating Integer Programming Models over Multiple Right-Hand Sides

References

• Aliev I, Henk M, Oertel T (2017) Integrality gaps of integer knapsack problems. Eisenbrand F, Koenemann J, eds. Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017 Waterloo, ON, Canada, June 26–28, 2017 Proceedings, Lecture Notes in Computer Science (Springer International Publishing, Cham, Switzerland), 25–38.Google Scholar
• Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Laurence J, ed. Proc. Fifth Internat. Conf. Oper. Res., vol. 69 (Tavistock Publications, London, United Kingdom), 447–454.Google Scholar
• Blair CE, Jeroslow RG (1977) The value function of a mixed integer program. I. Discrete Math. 19(2):121–138.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1979) The value function of a mixed integer program. II. Discrete Math. 25(1):7–19.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1982) The value function of an integer program. Math. Programming 23(1):237–273.Crossref, Google Scholar
• Blair CE, Jeroslow RG (1985) Constructive characterizations of the value function of a mixed-integer program II. Discrete Math. 10(3):227–240.Crossref, Google Scholar
• Cook W, Gerards AMH, Schrijver A, Tardos É (1986) Sensitivity theorems in integer programming. Math. Programming 34(3):251–264.Crossref, Google Scholar
• Eisenbrand F, Hähnle N, Pálvölgyi D, Shmonin G (2013) Testing additive integrality gaps. Math. Programming 141(1):257–271.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco).Google Scholar
• Gomory RE (1965) On the relation between integer and noninteger solutions to linear programs. Proc. Natl. Acad. Sci. USA 53(2):260–265.Crossref, Google Scholar
• Granot F, Skorin-Kapov J (1990) Some proximity and sensitivity results in quadratic integer programming. Math. Programming 47(1):259–268.Crossref, Google Scholar
• Higle JL, Wallace SW (2003) Sensitivity analysis and uncertainty in linear programming. Interfaces 33(4):53–60.Link, Google Scholar
• Hoşten S, Sturmfels B (2007) Computing the integer programming gap. Combinatorica 27(3):367–382.Crossref, Google Scholar
• Jeroslow RG (1979) Minimal inequalities. Math. Programming 17(1):1–15.Crossref, Google Scholar
• Johnson EL (1979) On the group problem and a subadditive approach to integer programming. Ann. Discrete Math. 5:97–112.Crossref, Google Scholar
• Johnson EL (1980) Subadditive lifting methods for partitioning and knapsack problems. J. Algorithms 1(1):75–96.Crossref, Google Scholar
• Khachiyan LG (1980) Polynomial algorithms in linear programming. USSR Comput. Math. Math. Physics 20(1):53–72.Crossref, Google Scholar
• Kong N, Schaefer AJ, Hunsaker B (2006) Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach. Math. Programming 108(2–3):275–296.Crossref, Google Scholar
• Mangasarian OL, Shiau TH (1987) Lipschitz continuity of solutions of linear inequalities, programs, and complementarity problems. SIAM J. Control Optim. 25(3):583–595.Crossref, Google Scholar
• Meyer RR (1974) On the existence of optimal solutions to integer and mixed-integer programming problems. Math. Programming 7(1):223–235.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Crossref, Google Scholar
• Paat J, Weismantel R, Weltge S (2020) Distances between optimal solutions of mixed-integer programs. Math. Programming 179:455–468.Crossref, Google Scholar
• Stein O (2016a) Error bounds for mixed integer linear optimization problems. Math. Programming 156(1):101–123.Crossref, Google Scholar
• Stein O (2016b) Error bounds for mixed integer nonlinear optimization problems. Optim. Lett. 10(6):1153–1168.Crossref, Google Scholar
• Tind J, Wolsey LA (1981) An elementary survey of general duality theory in mathematical programming. Math. Programming 21(1):241–261.Crossref, Google Scholar
• Trapp AC, Prokopyev OA, Schaefer AJ (2013) On a level-set characterization of the value function of an integer program and its application to stochastic programming. Oper. Res. 61(2):498–511.Link, Google Scholar
• Werman M, Magagnosc D (1991) The relationship between integer and real solutions of constrained convex programming. Math. Programming 51(1):133–135.Crossref, Google Scholar
• Williams HP (1996) Constructing the value function for an integer linear programme over a cone. Comput. Optim. Appl. 6(1):15–26.Crossref, Google Scholar
• Williams HP (2013) Model Building in Mathematical Programming, 5th ed. (John Wiley & Sons, New York).Google Scholar
• Wolsey LA (1981) Integer programming duality: Price functions and sensitivity analysis. Math. Programming 20(1):173–195.Crossref, Google Scholar