Branch-and-cut for cardinality optimization

dc.contributor.committeeChairFarias, Ismael R. d.
dc.contributor.committeeMemberKobza, John E.
dc.contributor.committeeMemberSmith, Milton L.
dc.creatorSikka, Ankit
dc.date.available2012-06-01T15:17:15Z
dc.date.issued2010-12
dc.degree.departmentIndustrial Engineering
dc.description.abstractA cardinality constrained linear programming problem (CCLP) is a linear programming problem with an additional constraint which restricts the number of nonnegative variables that may take on positive values. This problem arises in a large variety of applications, such as portfolio optimization, compressive sensing, metabolic engineering, and maximum feasible subsystem. In this thesis we review the branch-and-cut approach for CCLP, and we focus on the polyhedral approach to it. We rst present branching strategies to solve this model through branch-and-cut. To set the stage for important results on CCLP, we give some important results on the cardinality constrained knapsack polytope (CCKP). We then determine when the trivial inequalities de ne facets of CCKP. Finally, we discuss the nontrivial inequalities, which can be used as cuts in a branch-and-cut scheme.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2346/ETD-TTU-2010-12-1062
dc.language.isoeng
dc.rights.availabilityUnrestricted.
dc.subjectCardinality constraints
dc.subjectBranch-and-cut
dc.titleBranch-and-cut for cardinality optimization
dc.typeThesis
thesis.degree.departmentIndustrial Engineering
thesis.degree.disciplineIndustrial
thesis.degree.grantorTexas Tech University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science in Systems and Engineering Management

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
SIKKA-THESIS.pdf
Size:
276.13 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.12 KB
Format:
Plain Text
Description: