Discrete Approximations, Relaxations, and Applications in Quadratically Constrained Quadratic Programming
| dc.contributor.author | Beach, Benjamin Josiah | en |
| dc.contributor.committeechair | Hildebrand, Robert | en |
| dc.contributor.committeemember | Bish, Douglas R. | en |
| dc.contributor.committeemember | Ellis, Kimberly P. | en |
| dc.contributor.committeemember | Bansal, Manish | en |
| dc.contributor.department | Industrial and Systems Engineering | en |
| dc.date.accessioned | 2022-05-03T08:00:14Z | en |
| dc.date.available | 2022-05-03T08:00:14Z | en |
| dc.date.issued | 2022-05-02 | en |
| dc.description.abstract | We present works on theory and applications for Mixed Integer Quadratically Constrained Quadratic Programs (MIQCQP). We introduce new mixed integer programming (MIP)-based relaxation and approximation schemes for general Quadratically Constrained Quadratic Programs (QCQP's), and also study practical applications of QCQP's and Mixed-integer QCQP's (MIQCQP). We first address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a discrete-time nonconvex MIQCP, then approximate this model as a MILP using a discretization-based approach. We combine a rolling horizon approach with the discretization of individual chemical property specifications to deal with long scheduling horizons, time-varying quality specifications, and multiple suppliers with discrete arrival times. Next, we study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs). These SPs are parallel mechanisms that are stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. The robot will be used in concert with several other types robots to perform complex assembly missions in space. We develop algorithms and optimization models that can efficiently decide on favorable poses and movements that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger workspace and a greater overall payload capacity. In the third work, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions and formulate this approximation using mixed-integer programming (MIP). Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. We computationally demonstrate that our model outperforms existing MIP relaxations, and on hard instances can compete with state-of-the-art solvers. Finally, we study piecewise linear relaxations for solving quadratically constrained quadratic programs (QCQP's). We introduce new relaxation methods based on univariate reformulations of nonconvex variable products, leveraging the relaxation from the third work to model each univariate quadratic term. We also extend the NMDT approach (Castro, 2015) to leverage discretization for both variables in a bilinear term, squaring the resulting precision for the same number of binary variables. We then present various results related to the relative strength of the various formulations. | en |
| dc.description.abstractgeneral | First, we study a challenging long-horizon supply acquisition problem for a chemical plant. For this problem, constraints with products of variables are required to track raw material composition from supply carriers to storage tanks to the production feed. We apply a mixed-integer nonlinear program (MIP) approximation of the problem combined with a rolling planning scheme to obtain good solutions for industry problems within a reasonable time frame. Next, we study optimization methods applied to a robot designed as a stack of Stewart platforms (SPs), which will be used in concert with several other types robots to perform complex space missions. When chaining these SPs together, we obtain a robot that is generally stiffer more precise than a classic robot arm, enabling their potential use for a variety of purposes. Our methods can efficiently decide on favorable poses and movements for the robot that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger usable range of motion and a greater overall payload capacity. Our final two works focus on MIP-based techniques for nonconvex QCQP's. In the first work, we break down the objective into an easy-to-handle term minus some squared terms. We then introduce an elegant new MIP-based approximation to handle these squared terms. We prove that this approximation has strong theoretical guarantees, then demonstrate that it is effective compared to other approximations. In the second, we directly model each variable product term using a MIP relaxation. We introduce two new formulations to do this that build on previous formulations, increasing the accuracy with the same number of integer variables. We then prove a variety of useful properties about the presented formulations, then compare them computationally on two families of problems. | en |
| dc.description.degree | Doctor of Philosophy | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:34293 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/109787 | en |
| dc.language.iso | en | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | Creative Commons Attribution 4.0 International | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | en |
| dc.subject | Quadratically Constrained Quadratic Programming | en |
| dc.subject | Mixed Integer Programming approximations | en |
| dc.subject | Binarization | en |
| dc.title | Discrete Approximations, Relaxations, and Applications in Quadratically Constrained Quadratic Programming | en |
| dc.type | Dissertation | en |
| thesis.degree.discipline | Industrial and Systems Engineering | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | doctoral | en |
| thesis.degree.name | Doctor of Philosophy | en |