FINITE DISJUNCTIVE PROGRAMMING METHODS FOR GENERAL MIXED INTEGER LINEAR PROGRAMS

Persistent Link:
http://hdl.handle.net/10150/145120
Title:
FINITE DISJUNCTIVE PROGRAMMING METHODS FOR GENERAL MIXED INTEGER LINEAR PROGRAMS
Author:
Chen, Binyuan
Issue Date:
2011
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
In this dissertation, a finitely convergent disjunctive programming procedure, the Convex Hull Tree (CHT) algorithm, is proposed to obtain the convex hull of a general mixed–integer linear program with bounded integer variables. The CHT algorithm constructs a linear program that has the same optimal solution as the associated mixed-integer linear 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 optimal solution of the general mixed-integer linear program with bounded integer variables in finitely many steps. We also enhance the CPT algorithm with several techniques including a “round-of-cuts” approach and an iterative method for solving the cut generation linear program (CGLP). Two normalization constraints are discussed in detail for solving the CGLP. For moderately sized instances, our study shows that the CPT algorithm provides significant gap closures with a pure cutting plane method.
Type:
Electronic Dissertation; text
Keywords:
cutting plane; finite convergence; convex hull; disjunctive programming; mixed-integer linear program
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems & Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Sen, Suvrajeet; Bayraksan, Güzin

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleFINITE DISJUNCTIVE PROGRAMMING METHODS FOR GENERAL MIXED INTEGER LINEAR PROGRAMSen_US
dc.creatorChen, Binyuanen_US
dc.contributor.authorChen, Binyuanen_US
dc.date.issued2011-
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractIn this dissertation, a finitely convergent disjunctive programming procedure, the Convex Hull Tree (CHT) algorithm, is proposed to obtain the convex hull of a general mixed–integer linear program with bounded integer variables. The CHT algorithm constructs a linear program that has the same optimal solution as the associated mixed-integer linear 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 optimal solution of the general mixed-integer linear program with bounded integer variables in finitely many steps. We also enhance the CPT algorithm with several techniques including a “round-of-cuts” approach and an iterative method for solving the cut generation linear program (CGLP). Two normalization constraints are discussed in detail for solving the CGLP. For moderately sized instances, our study shows that the CPT algorithm provides significant gap closures with a pure cutting plane method.en_US
dc.typeElectronic Dissertationen_US
dc.typetexten_US
dc.subjectcutting planeen_US
dc.subjectfinite convergenceen_US
dc.subjectconvex hullen_US
dc.subjectdisjunctive programmingen_US
dc.subjectmixed-integer linear programen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems & Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSen, Suvrajeeten_US
dc.contributor.advisorBayraksan, Güzinen_US
dc.contributor.committeememberZeng, Danielen_US
dc.contributor.committeememberSzidarovszky, Ferencen_US
dc.contributor.committeememberKüçükyavuz, Simgeen_US
dc.identifier.proquest11526-
dc.identifier.oclc752261390-
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.