  


Finite Disjunctive Programming Characterizations for General MixedInteger Linear Programs
Binyuan Chen (bychenemail.arizona.edu) Abstract: In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixedinteger linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard notion of sequential cutting planes with ideas underlying the convex hull tree algorithm to help guide the choice of disjunctions to use within a cutting plane method. This algorithm, which we refer to as the cutting plane tree algorithm, is shown to converge to an integral optimal solution in finitely many iterations. Finally, we illustrate the proposed algorithm on three wellknown examples in the literature that require an infinite number of elementary or split disjunctions in a rudimentary cutting plane algorithm. Keywords: Mixedinteger programming, disjunctive programming, convex hull, finite convergence Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Technical report, Data Driven Decisions Lab, The Ohio State University Download: [PDF] Entry Submitted: 08/25/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  