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 15 of 15 for “"Cutting Plane Methods"”.
-
Interior Point Cutting Plane Methods in Integer Programming
… Particularly, we use the analytic center cutting plane method to improve three of the main components of the branch-and-bound algorithm: cutting planes, heuristics, and branching. First, we present an interior point branch-and-cut algorithm for structured integer programs based on Benders …
-
Primal Cutting Plane Methods for the Traveling Salesman Problem
… problem (TSP) are based on the dual fractional cutting plane approach, which moves from one lower bound to the next. This thesis describes methods for implementing a TSP solver based on a primal cutting plane approach, which moves from tour to tour with non-degenerate primal simplex pivots and …
-
Investigation of k-rationality & cutting plane methods in sequentially connected 2D assignment problems
… optimization problem, and utilize different methods to recover near-optimal integer solutions’. This thesis explores the usage of such approaches in the context of the Time-extended Generalised Optimal Sub-Pattern Assignment (TGOSPA) metric—a performance measure for the evaluation of multiple …
-
Network Target Coordination for Design Optimization of Decomposed Systems
… research has shown that various coordination methods obtain different solution accuracies and exhibit different computational efficiencies when solving a decomposed system. Addressing these coordination decisions may lead to improved complex system design. This dissertation studies …
-
Specialized solvers for structured convex programs in high-dimensional statistics
… convex programming solvers such as cutting-plane methods and interior-point methods often struggle to scale efficiently in high-dimensional or large-scale settings. To address these limitations, we develop specialized algorithms that bypass the computational bottlenecks of black-box …
-
Algorithms for solving linear integer progamming problems
<p>This thesis discusses several methods used to solve linear integer programming problems. Chapters 1-3 give the necessary linear programming background. Chapter 4 introduces integer programming and describes, in general, the two classes of solution methods -enumeration and cutting planes. Chapter …
-
Solving the integer linear programming problem
… development and the workings of some selected methods to solve the integer linear programming problem.</p><p>Chapter I introduces the general theory of linear programming. Both the simplex and the dual simplex method are introduced along with a summary of the general steps of the …
-
New valid inequalities for a time-indexed formulation of the flexible job shop scheduling problem
… testing. This has been performed using a cutting-plane method on Fattahi test instances, both with the objective of minimizing makespan as well as minimizing tardiness. For both objectives the new valid inequalities have yielded improved lower bounds, however with varying effect. …
-
Some Problems in Conic, Nonsmooth, and Online Optimization
… to solve general SDPs via interior-point methods. Conceptually, our result for this general problem resolves the prior paradox of cutting-plane methods being faster at solving SDPs than interior-point methods, despite the former tracking far less structural information about the iterates. …
-
Covering relaxation methods for solving the zero-one positive polynomial programming problem
… the newly introduced accelerated algorithm are cutting plane algorithms in which the relaxed problem is the set covering problem and the cutting planes are linear covering constraints. In contrast with other cutting plane methods in integer programming, the accelerated covering relaxation …
-
Topics in Statistics and Convex Geometry: Rounding, Sampling, and Interpolation
… John’s ellipsoid in particular. We also discuss cutting plane methods and Vaidya’s algorithm, which we employ in subsequent analysis. We then review Markov chains on general state spaces to motivate designing rapidly mixing geometric random walks, and the means by which the mixing time may be …
-
An exploration of stochastic decomposition algorithms for stochastic linear programs with recourse
… can be described as decomposition based cutting plane methods in which the cuts are estimated from random samples. Moreover, the algorithms all use the incremental sampling plan inherent to the Stochastic Decomposition (SD) algorithm developed by Higle and Sen in 1991. Our study includes …
-
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 …
-
Analysis and Control of Neural Network Dynamical Systems
… (i.e., synthesizing a Lyapunov function using cutting-plane methods) analysis frameworks. In hope of combining robust model predictive control (MPC) and NN verification tools for safe control of NN dynamical systems, in the second part of the thesis, we propose a novel robust MPC method for …
-
Nash equilibrium problems in power markets and product design: Analysis and algorithms
… massive stochastic program. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample-space. Insights regarding market design and operation are obtained after testing the model on a 53-node electricity network. The …