Date of Award
12-2018
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematical Sciences
Committee Member
Warren P. Adams, Committee Chair
Committee Member
Boshi Yang
Committee Member
J. Cole Smith
Committee Member
Matthew J. Saltzman
Committee Member
Akshay S. Gupte
Abstract
This research derives improved mathematical representations for various expressions of binary variables. There are three main efforts, consisting of: the Target Visitation Problem (TVP), the Quadratic Linear Ordering Problem (QLOP), and a special family of monomials of binary variables. For the first two efforts, which are known in the literature to be (mixed) 0-1 programs, we derive new families of valid inequalities that tighten existing forms and lead to superior performance. We give computational experience to show the advantages of our approaches. For the third effort, we provide an explicit convex hull representation for special forms of monomials of binary variables that arise in 0-1 polynomial programs; this convex hull form generalizes a classical linearization result. Relative to the first effort, the TVP is a hybrid between the well-known Traveling Salesman Problem (TSP) and the Linear Ordering Problem (LOP). Both the TSP and LOP seek an “optimal” permutation of a collection of objects, but they differ in the manner in which the objective is defined. For each distinct pair of objects, the TSP incurs a cost when the first object immediately precedes the second, while the LOP realizes a reward when the first object anywhere precedes the second. The TVP incurs both the cost and reward. Our contribution is a new family of valid linear inequalities that are derived by exploiting the structure of the decision variables. This family is a strengthened version of the well-known Miller-Tucker-Zemlin inequalities for the TSP. The inequalities are derived via a two-step approach; the first step uses a conditional logic argument to compute valid quadratic inequalities, and the second step suitably surrogates these inequalities to eliminate the quadratic terms. Computational experience shows the advantage of using these inequalities within a commercial solver. While the emphasis is on the TVP, we show how this logic is applicable to other families of problems. For the second effort, the QLOP is a generalization of the LOP that, in addition to having linear rewards, also realizes rewards for products of pairwise orderings. Such products naturally lead to quadratic terms in the objective function. We exploit the problem structure to obtain three key results. First, we provide a lifting theorem which establishes that every facet-defining inequality (facet) for the convex hull of solutions on n objects is a facet for any collection of more than n objects. Such a result is known for the LOP but the complex structure of the QLOP necessitates a more involved argument. Second, we give an explicit listing of all the facets for the convex hull of the size n = 3 case; this listing allows for a mixed 0-1 linear form of the general size-n QLOP that uses only half the number of inequalities in the same variable space as recent work, while maintaining the same linear programming strength. Third, we give all the facets for the convex hull of the size n = 4 case. The facets are characterized into five general families. We provide computational experience that shows the merits of reduced numbers of constraints in a solution strategy, and we also examine the tightening effects of each of the five families. For the third effort, we give the convex hull of any monomial in n binary variables x that has the characteristic that each variable is bounded above by an auxiliary binary variable y. Without y, the convex hull is known to be obtained by replacing the monomial with a continuous variable, and then enforcing (n + 2) linear inequalities to ensure that the new variable equals the monomial value at all binary realizations. In the presence of y, we separately consider the cases having n = 2 and n ≥ 3. We show that when n = 2, an implementation of a special-structure reformulation- linearization-technique (RLT) gives the convex hull, while for n ≥ 3 we employ a different level-1 RLT implementation, in concert with the known convex hull result, to accomplish the same task. The argument for n ≥ 3 allows extensions to convex hulls of various discrete and/or continuous sets including, for example, restricted forms of both special symmetric multilinear functions over box constraints and the Boolean Quadric Polytope.
Recommended Citation
DeVries, Audrey N., "Tight Representations of Specially-Structured 0-1 Linear, Quadratic, and Polynomial Programs" (2018). All Dissertations. 2246.
https://open.clemson.edu/all_dissertations/2246