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 140 for “"cutting plane"”.

  1. Multi-row approaches to cutting plane generation

    This thesis focuses on the use of cutting-plane 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 …

    liege Repository record for Multi-row approaches to cutting plane generation (opens in a new tab) Download PDF for Multi-row approaches to cutting plane generation (opens in a new tab)

  2. 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 …

    waterloo Repository record for Interior Point Cutting Plane Methods in Integer Programming (opens in a new tab)

  3. 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 …

    waterloo Repository record for Primal Cutting Plane Methods for the Traveling Salesman Problem (opens in a new tab)

  4. Parallel cutting plane algorithms for inverse mixed integer linear programming

    <p>We present parallel cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which are extended algorithms of the cutting plane algorithms for InvMILP. It improves the efficiency of the original algorithm and provides feasible solutions before terminating …

    iastate Repository record for Parallel cutting plane algorithms for inverse mixed integer linear programming (opens in a new tab)

  5. Investigation of k-rationality & cutting plane methods in sequentially connected 2D assignment problems

    … k-rationality and the other on using different cutting plane methods derived from fractional Gomory cuts. The results suggests that k-rationality is numerically unsuitable for this specific problem, and that the Gomory-based cutting methods lack performance consistency. Finally, an outline of …

    chalmers Repository record for Investigation of k-rationality & cutting plane methods in sequentially connected 2D assignment problems (opens in a new tab)

  6. Enhanced intersection cutting plane and reformulation-linearization enumeration based approaches for linear complementarity problems

    … approach, we develop an enhanced intersection cutting plane algorithm for solving LCP. The matrix <i>M</i> is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions …

    vt Repository record for Enhanced intersection cutting plane and reformulation-linearization enumeration based approaches for linear complementarity problems (opens in a new tab)

  7. Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems

    … (SDP) relaxation model that incorporates cutting planes proposed recently by Anjos, Kennings, and Vannelli (AKV) was considered a breakthrough in the field. This thesis presents a new SDP model AKV' and compares the two relaxations. The AKV' is largely based on the previous model, but it …

    waterloo Repository record for Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems (opens in a new tab)

  8. Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem

    This thesis has two 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 …

    waterloo Repository record for Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem (opens in a new tab)

  9. Methods for solution to the integer linear programming problem

    … the feasible solution set by introduction of cutting plane constraints, and the method of reducing the ILP to a knapsack formulation.</p><p>Chapter I introduces the ILP and the theoretical basis for the cutting plane approach, along with a method for choosing the cutting plane. The all-integer …

    ut-knoxville Repository record for Methods for solution to the integer linear programming problem (opens in a new tab)

  10. 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 …

    gatech Repository record for Theory and computation of sparse cutting planes (opens in a new tab)

  11. Finding violated cut constraints for the STSP using a decomposition approach

    … STSP. In this thesis, we develop a new parallel cutting plane approach for solving the SEP. In this approach, many violated cuts are found at each stage by decomposing the current solution into a set of nicely structured points, and then searching for violations in these points in parallel by …

    ottawa-retro Repository record for Finding violated cut constraints for the STSP using a decomposition approach (opens in a new tab)

  12. FINITE DISJUNCTIVE PROGRAMMING METHODS FOR GENERAL MIXED INTEGER LINEAR PROGRAMS

    … program. The standard notion of sequential cutting planes is then combined with ideasunderlying the CHT algorithm to help guide the choice of disjunctions to use within a new cutting plane method, the Cutting Plane Tree (CPT) algorithm. We show that the CPT algorithm converges to an integer …

    arizona-thes Repository record for FINITE DISJUNCTIVE PROGRAMMING METHODS FOR GENERAL MIXED INTEGER LINEAR PROGRAMS (opens in a new tab)

  13. An integer polyhedron related to the design of survivable communication networks.

    The linear programming cutting plane method has proven to be quite successful for solving certain "hard" combinatorial optimization problems, c.f. (1), (6), (12), (24), (26). A great deal of this success is due to the use of problem specific cutting planes which define facets of the underlying …

    ottawa-retro Repository record for An integer polyhedron related to the design of survivable communication networks. (opens in a new tab)

  14. Algorithms for solving linear integer progamming problems

    … two classes of solution methods -enumeration and cutting planes. Chapter 5 details two specific cutting plane methods, one all-integer approach and one fractional approach.Chapter 6 describes the branch-and-bound method, one of the enumeration methods. In Chapter 7 the additive algorithm for 0-1 …

    ut-knoxville Repository record for Algorithms for solving linear integer progamming problems (opens in a new tab)

  15. The extreme point mathematical programming problem

    … Lattice Point Problem. We obtain a variety of cutting plane algorithms and analyze the convergence of such algorithms. Insightful examples of nonconvergence are also provided. Two finitely convergent algorithms are also presented. One of these is a cutting plane based procedure while the other …

    vt Repository record for The extreme point mathematical programming problem (opens in a new tab)

  16. The symmetric generalized traveling salesman problem

    … to investigate a linear programming (LP) based cutting plane procedure for bounding the symmetric version of the GTSP. In the symmetric version of the problem, the distance associated with travel from city i to city j is the same as from city j to city i. The cutting plane procedure utilizes …

    utk-theses Repository record for The symmetric generalized traveling salesman problem (opens in a new tab)

Page 1 of 7