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 20 of 103 for “"cutting planes"”.
-
Theory and computation of sparse cutting planes
Cutting plane plays an important role in the theory and computation of integer programming. Nowadays, most state-of-the-art integer programming solvers tend to bias their cutting plane selection towards sparse ones, which emphasizes the significance of sparse cutting planes. In this thesis, we …
-
On Linear Programming, Integer Programming and Cutting Planes
In this thesis we address three related topic in the field of Operations Research. Firstly we discuss the problems and limitation of most common solvers for linear programming, precision. We then present a solver that generate rational optimal solutions to linear programming problems by solving a …
-
Cutting Planes for Large Mixed Integer Programming Models
In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general …
-
Algorithms for Stochastic Integer Programs Using Fenchel Cutting Planes
… develops theory and methodology based on Fenchel cutting planes for solving stochastic integer programs (SIPs) with binary or general integer variables in the second-stage. The methodology is applied to auto-carrier loading problem under uncertainty. The motivation is that many applications can be …
-
Cutting planes in mixed integer programming: theory and algorithms
… and in particular, we discuss the role of cutting planes and our contributions to this theory. In Chapter 2, we investigate the Gomory mixed integer cut from the perspective of group polyhedra. In this setting, the mixed integer cut appears as a facet of the master cyclic group polyhedron. …
-
Exploiting structure in mixed integer programming: Branching, cutting planes, and complexity
… faster through novel branching schemes and novel cutting planes. Via computational complexity analysis, we also justify the usage of MIPs for approaching challenging problems and inspire the design of primal heuristics. The first part of the thesis focuses on novel branching schemes. We explore …
-
INVESTIGATING THE EXACT EFFECTIVENESS OF CUTTING PLANES OVER BRANCH-AND-BOUND IN INTEGER PROGRAMMING
… thesis investigates the exact effectiveness of cutting plane (CP) methods relative to branch-and-cut (BC) techniques in convex 0/1 integer programming under variable disjunctions, with a focus on the three-dimensional setting. We prove that for a range of three-dimensional convex 0/1 integer …
-
On the development of cut-generating functions
Cut-generating functions are tools for producing cutting planes for generic mixed-integer sets. Historically, cutting planes have advanced the progress of algorithms for solving mixed- integer programs. When used alone, cutting-planes provide a finite time algorithm for solving a large family of …
-
The Proof Complexity of Integer Programming
… Schoenebeck08]. One notable exception is the Cutting Planes system, which formalizes classical algorithms for integer programming. In this thesis we confirm this conjecture for Cutting Planes. Modern algorithms for integer programming, known as branch-and-cut, improve upon Cutting Planes by …
-
Valid inequalities and computational results for SOS1-, SOS2-, and cardinality-constrained linear programs
… SOS2, and cardinality. We study and develop cutting planes for those types of constraints, and use them within branch-and-cut to solve difficult MIP instances. Our computational results indicate that the cutting planes used are very effective in reducing the solution times of our instances. …
-
Consistency in integer programming
In this thesis, we study the role of cutting planes in reducing the size of the branch-and-bound tree for integer programs. Cutting planes are traditionally used to tighten relaxations of the problem by excluding fractional solutions, which leads to improving the dual bounds. In this research, we …
-
On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems
… able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs. Extensive …
-
A Path Paved by Proof Complexity Towards Verifying Nonlinear Integer Arithmetic
… that pseudo-Boolean solvers equipped with cutting planes reasoning have the potential to combine the complementary strengths of the existing SAT and algebraic approaches while avoiding their weaknesses. We present several results on the proof complexity of fundamental multiplier identities. …
-
Cutting and packing : problems, models and exact algorithms
… programming models and exact algorithms for hard cutting and packing problems are addressed. We consider in particular the combinatorial problems of this family that are defined over a single dimension. The optimization procedures rely on tools from the field of integer programming, namely column …
-
3D modelling using partial differential equations (PDEs).
… the intersection of horizontal and vertical mesh cutting planes. The set of sampled points contains the explicit structure of the cutting planes with three important consequences: 1) points in the plane can be defined as a one dimensional signal and are thus, subject to a number of compression …
-
Subgradient-based Decomposition Methods for Stochastic Mixed-integer Programs with Special Structures
… decomposition of the problem and Fenchel cutting planes. The algorithm combines progressive hedging to restore nonanticipativity of the first-stage solution, and generates Fenchel cutting planes for the LP relaxations of the subproblems to recover integer solutions. A computational study …
-
Split Cuts From Sparse Disjunctions
Cutting planes are one of the major techniques used in solving Mixed-Integer Linear 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 …
Page 1 of 6