Addressing formulation size, strength, and mathematical structure in modelling discrete decision problems

An important step in solving a decision problem is the construction of a mathematical representation that accurately depicts the physical scenario, and also lends itself to effective optimization methods. For many problems, the formulation is critical in that it dictates whether an optimal strategy can be obtained and verified.; This effort focuses on the celebrated family of mixed 0–1 polynomial programs. The name derives from the mathematical form. For such problems, there can exist a mixture of both discrete and continuous variables, and the objective and constraints are polynomial functions. These problems have commanded widespread attention because of the large number of motivating applications, and because of their resistance to solution strategies.; The challenge of constructing a “favorable” mathematical representation typically centers around obtaining an attractive mixed 0–1 linear program. In this manner, linear programming relaxations to the original problem can be obtained by treating the binary variables as continuous. The relaxations give polyhedral approximations to the convex hull of feasible points, and can occur in the original or higher-dimensional spaces. An attractive formulation is usually measured in terms of various criteria: for example, size, approximation strength, and mathematical structure. This dissertation makes three distinct contributions to the reformulation process, keeping in mind each of these criteria.; The first contribution shows how variations of a classical linearization method for quadratic programs can be generalized to handle cubic and higher-degree problems. More recent strategies are suitably characterized, and improvements are exposed.; The second contribution compares two known linearization methods for quadratic programs, and suggests an approach that combines the attractive features of each. The first method provides concise reformulations with weak relaxations while the second gives larger representations with tight relaxations. The combined method blends the conciseness of the first with the tightness of the second. Special structures in the constraints that lead to further reductions in problem size and increased strength are also examined.; Finally, an algorithm for exploiting the block-diagonal structure of a linear formulation is developed. Relationships to published methods are discussed, and computational experience is provided for the 0–1 quadratic knapsack problem.