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 10 of 10 for “"Valid inequality"”.
-
Algoritmos non delayed relax-and-cut para o problema do caixeiro viajante assimétrico
… obtaining viable primal solutions. As well as valid inequality separation procedures for PCVA, in order to evaluate the impact caused by stronger Lagrangean limiters.
-
Single-Scenario Facet Preservation for Stochastic Mixed-Integer Programs
… form of an SMIP. Given a facet-defining valid inequality for a single-scenario version of the SMIP, we provide conditions under which the same inequality remains facet-defining for the extensive form. Our main result gives necessary and sufficient conditions for a facet-defining …
-
Exploring Structure and Reformulations in Different Integer Programming Algorithms
… We start by addressing the ques- tion of lifting valid inequalities, i.e. finding a valid inequality for a set Y from the knowledge of a valid inequality for a lower-dimensional restriction X of Y . We simplify and clarify the presentation of the procedure. This allows us to derive conditions …
-
INVESTIGATING THE EXACT EFFECTIVENESS OF CUTTING PLANES OVER BRANCH-AND-BOUND IN INTEGER PROGRAMMING
… convex 0/1 integer programming problems, any valid inequality established by a BC proof tree can be derived by a corresponding pure CP proof tree with zero slack. Our approach combines structural induction and detailed geometric case analysis to systematically transform mixed BC proofs into …
-
Resource constrained shortest paths and extensions
… the single resource case and obtain several new valid inequality classes. Separation routines are provided, along with a polynomial time algorithm for constructing an auxiliary conflict graph which can be used to separate well known valid inequalities for the node packing polytope. We establish …
-
Monitoring on Graphs: An Exploration into k-Cores, Zero Forcing, and Power Domination
… edge and cycle transversals of the graph give valid inequalities for the convex hull of the k-core polytope - which can be further generalized to a family of l-core transversals. Further, a heuristic for the hitting set of the minimal l-cores is given with its associated valid inequality. …
-
Exact Approaches for a Class of Nonlinear Discrete Facility Location and Network Design Problems
… We further strengthen the MISOCPs by adding valid inequality cuts. The first paper of this thesis investigates a class of discrete stochastic facility location problems with congestion. The problem is to simultaneously determine the location and the capacity level of the facilities, as well …
-
Comparing Intersection Cut Closures using Simple Families of Lattice-Free Convex Sets
… cut generation procedure is to produce a linear inequality that separates a given infeasible point x* (usually a basic feasible solution of the linear programming relaxation) from the set of feasible solutions for the problem at hand. Early and well-known cut generation procedures rely on …
-
Facets of conflict hypergraphs
… generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments …
-
Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout Problem
… this dissertation, we introduce new families of valid inequalities for general linear mixed integer programs (MIPs) and second-order conic MIPs (SOCMIPs) and establish several theoretical properties and computational effectiveness of these inequalities. First we introduce the mixed n-step mixed …