Branch-and-cut for complementarity-constrained linear programs

Simple item page
dc.contributor.committeeChairde Farias, Ismael R., Jr.
dc.contributor.committeeMemberCross, Jennifer A.
dc.contributor.committeeMemberHowle, Victoria E.
dc.contributor.committeeMemberWang, Shiren
dc.contributor.committeeMemberSmith, Philip W.
dc.creatorDing, Li
dc.date.available2015-06-18T20:27:12Z
dc.date.issued2015-05
dc.description.abstractA Complementarity-Constrained Linear Program (CCLP) is a linear program which has additional constraints called complementarity constraints. Which are such that, for some sets of variables, at most one variable can be positive. Numerous real world problems, such as resource allocation problems, can be mapped into CCLP. Traditionally, these problems are formulated as conventional MIP problems by introducing additional binary variables and adding new constraints. In the alternative approach we proposed in this dissertation, continuous variables are kept in the model. We will derive valid inequalities (called cutting planes) for the convex hull of the feasible set, which are then added to the cut pool in a branch-and-cut algorithm. We will present three families of valid inequalities, two of which are obtained by lifting valid inequalities of the projected polytope.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2346/62363
dc.language.isoeng
dc.rights.availabilityUnrestricted.
dc.subjectSpecial Ordered Sets
dc.subjectSOS1
dc.subjectMixed-Integer Programming
dc.subjectBranch-and-Cut
dc.subjectCutting Planes, Lifting
dc.titleBranch-and-cut for complementarity-constrained linear programs
dc.typeThesis
thesis.degree.departmentIndustrial Engineering
thesis.degree.disciplineIndustrial Engineering
thesis.degree.grantorTexas Tech University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
DING-DISSERTATION-2015.pdf
Size:
1.52 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

Electronic Theses and Dissertations