Diameter Polytopes of Feasible Binary Programs

arXiv2008.06844MaRDI QIDQ6347147

Author name not available (Why is that?)

Publication date: 16 August 2020

Abstract: Feasible binary programs often have multiple optimal solutions, which is of interest in applications as they allow the user to choose between alternative optima without deteriorating the objective function. In this article, we present the optimal diameter of a feasible binary program as a metric for measuring the diversity among all optimal solutions. In addition, we present the diameter binary program whose optima contains two optimal solutions of the given feasible binary program that are as diverse as possible with respect to the optimal diameter. Our primary interest is in the study of the diameter polytope, i.e., the polytope underlying the diameter binary program. Under suitable conditions, we show that much of the structure of the diameter polytope is inherited from the polytope underlying the given binary program. Finally, we apply our results on the diameter binary program and diameter polytope to cases where the given binary program corresponds to the linear ordering problem and the symmetric traveling salesman problem.

Has companion code repository: https://github.com/trcameron/Diameter-Polytopes

This page was built for publication: Diameter Polytopes of Feasible Binary Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347147)