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 5 of 5 for “"Split cuts"”.
-
Split Cuts From Sparse Disjunctions
… Programming (MIP) models. Various types of cuts have long been exploited by MIP solvers, leading to state-of-the-art performance in practice. Among them, the class of split cuts, which includes Gomory Mixed Integer (GMI) and Mixed Integer Rounding (MIR) cuts from tableaux, are arguably the …
-
Fundamental properties of convex mixed-integer programs
… fifth part, we study some generalizations of the split closure in the case of linear MIPs. Split cuts form a well-known class of valid inequalities for linear MIPs. Cook et al. (1990) showed that the split closure of a rational polyhedron - that is, the set of points in the polyhedron satisfying …
-
ON THE COMPLEXITY OF MIXED INTEGER PROGRAMMING
… polynomial time cutting plane algorithm based on split cuts to solve integer programs in two-dimensional space. In addition, we show that one can use branching to enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero …
-
Topics in discrete optimization: models, complexity and algorithms
… We first provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the …
-
Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem
… main 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 …