1,721,032 research outputs found
Optimal Cutting Planes from the Group Relaxations
Get PDFWe study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson's finite and infinite group models and we describe the valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the finite group model of prime order, we show that the unique maximizer is an automorphism of the Gomory Mixed-Integer (GMI) cut for a possibly different finite group problem of the same order. We extend the notion of volume of a simplex to the infinite dimensional case. This is used to show that in the infinite group model, the GMI cut maximizes the volume of the nonnegative orthant cut off by an inequality
A geometric approach to cut-generating functions
No full textThe cutting-plane approach to integer programming was initiated more that 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for several decades until relatively recently, when a paper of Andersen, Louveaux, Weismantel and Wolsey generated renewed interest in the corner polyhedron and intersection cuts. Recent developments rely on tools drawn from convex analysis, geometry and number theory, and constitute an elegant bridge between these areas and integer programming. We survey these results and highlight recent breakthroughs in this area
The structure of the infinite models in integer programming
Get PDFThe infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to describe finite dimensional corner polyhedra with rational data. We also discover new facts about corner polyhedra with non-rational data
A Large Neighborhood Search Heuristic for Naval Re-Supply
Get PDFThe U.S. Military faces a myriad of optimization problems when planning re-supply of their forces. Re-supply planning must keep pace with technological advancements to other aspects of military operations so that the U.S. can remain competitive with potential adversaries.
The Logistics Aid for Sustainment and Expeditionary Readiness (LASER) employs a large neighborhood search (LNS) algorithm to modernize naval re-supply planning in the military. Preliminary results indicate that the LNS algorithm provides dramatic performance benefits compared to a more traditional, mixed integer programming approach
Extension of Chvátal-Gomory Closure via K-Halfspace closure
Get PDFWe propose further generalizations of Chvátal-Gomory closure, extending on previous works where the two-halfspace closure is analyzed. Here, we analyze the method of computing the convex hull of integer points by using the intersection of k-halfspaces as cutting planes. We prove that there exists examples where there is a significant improvement between the number of three-halfspace closure operations and two-halfspace closure. We also provide simulations on a potential approach to extend this to four-halfspaces, and potentially even higher numbers, along with a conjecture on the relationship between these operations
INVESTIGATING THE EXACT EFFECTIVENESS OF CUTTING PLANES OVER BRANCH-AND-BOUND IN INTEGER PROGRAMMING
Get PDFThis 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 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 CP-only proofs. In contrast to earlier ideas based on cut rotation or local approximation, our method fully replaces branching without increasing the overall proof size.
Although our results are currently limited to the three-dimensional case, they provide the first evidence that the finite substitution result may hold in low dimensions. Extending this to higher dimensions remains an open challenge
INVESTIGATING THE EXACT EFFECTIVENESS OF CUTTING PLANES OVER BRANCH-AND-BOUND IN INTEGER PROGRAMMING
Get PDFThis 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 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 CP-only proofs. In contrast to earlier ideas based on cut rotation or local approximation, our method fully replaces branching without increasing the overall proof size.
Although our results are currently limited to the three-dimensional case, they provide the first evidence that the finite substitution result may hold in low dimensions. Extending this to higher dimensions remains an open challenge
Extension of Chvátal-Gomory Closure via K-Halfspace closure
Get PDFWe propose further generalizations of Chvátal-Gomory closure, extending on previous works where the two-halfspace closure is analyzed. Here, we analyze the method of computing the convex hull of integer points by using the intersection of k-halfspaces as cutting planes. We prove that there exists examples where there is a significant improvement between the number of three-halfspace closure operations and two-halfspace closure. We also provide simulations on a potential approach to extend this to four-halfspaces, and potentially even higher numbers, along with a conjecture on the relationship between these operations
- …
