Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 8 of 8 for “"Integer hull"”.
-
Fundamental properties of convex mixed-integer programs
… of various fundamental concepts in convex mixed-integer programs (MIPs), that is, optimization problems where all the decision variables belong to a given convex set and, in addition, a subset of them are required to be integer. In particular, we study properties of their feasible region and …
-
Topics in group methods for integer programming
… a slope with the corresponding Gomory mixed-integer cut. We give a new three-slope facet which is independent of the GMIC and also give a four-slope T-space facet construction, which to our knowledge, is the first four-slope construction. We describe an enumerative framework for the discovery …
-
Strong convex relaxations for quadratically constrained quadratic programs
… is bounded, then cut generating functions for integer linear programs can easily be adapted to give the integer hull of the conic integer program. We then introduce a new class of cut generating functions which are non-decreasing with respect to the second-order cone. We show that, under some …
-
On the matrix cuts of Lovasz and Schrijver and their use in integer programming
… iterations for polyhedra in n-space, the convex hull of 0-1 vectors. We study the complexity of matrix-cut based methods for solving 0-1 integer linear programs. We first prove bounds on the (rank) number of iterations required to obtain the integer hull. We show that the upper bound of n, …
-
Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees
… (UFPP). For these problems, when the natural integer programming formulation is relaxed to a linear program, the integrality gap is O(n). Previous work on UFPT and UFPP has established that the addition of rank constraints to the linear program can be effective in some cases at reducing the …
-
Multi-row approaches to cutting plane generation
… techniques to improve general-purpose mixed-integer linear programming solvers. The first topic covered here is a fast separation method for two-row cuts. Two-row cuts are intersection cuts from two rows of a simplex tableau describing the LP relaxation of the problem. This type of cuts …
-
A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization
… these hard problems is to formulate them as integer programs (which themselves are hard to solve), and then approximate their feasible regions using sets that are easier to describe and optimize over. Two of the most prominent mathematical models that are used to obtain these approximations …
-
Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem
… themes, both centered around the role of cuts in integer programming and approximation algorithms. In the first part, we investigate the complexity of split closures in mixed-integer sets in~$\mathbb{R}^3$ with two integral variables and one continuous variable. While it is known that …