  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.
