{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/86845"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/86845","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Polyhedra Study of Mixed Integer Programs With Variable Upper Bounds","abstract":"We investigate the convex hull of the set defined by a single constraint with continues and binary variables and in addition, variable upper bound constraints are present. We introduce the flow cover inequality, which is valid for a projection. We also give conditions under which this inequality is facet defining. We use sequence independent lifting to obtain valid inequalities for the entire set. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. In the second part of the thesis we first elaborate on general sequence dependent lifting for this set and present a dynamic program for calculating lifting coefficients. Then we consider projections of this set to knapsack cover and to the single binary variable polytope. We present the result of sequence independent lifting of the knapsack cover inequality and obtain lifting some coefficients for sequence dependent lifting with for specific sequences. We generate two new families of facet defining inequalities for the single binary variable polytope and prove that combined with the trivial inequalities they give a full description of this polytope. Finally, we give an optimization problem for the lifting coefficients.","abstract_html":"We investigate the convex hull of the set defined by a single constraint with continues and binary variables and in addition, variable upper bound constraints are present. We introduce the flow cover inequality, which is valid for a projection. We also give conditions under which this inequality is facet defining. We use sequence independent lifting to obtain valid inequalities for the entire set. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. In the second part of the thesis we first elaborate on general sequence dependent lifting for this set and present a dynamic program for calculating lifting coefficients. Then we consider projections of this set to knapsack cover and to the single binary variable polytope. We present the result of sequence independent lifting of the knapsack cover inequality and obtain lifting some coefficients for sequence dependent lifting with for specific sequences. We generate two new families of facet defining inequalities for the single binary variable polytope and prove that combined with the trivial inequalities they give a full description of this polytope. Finally, we give an optimization problem for the lifting coefficients.","abstract_has_math":false,"creators":["Shebalov, Sergey"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Diego Klabjan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-28T15:19:49Z","date_published":"2015-09-28T15:19:49Z","updated_at":"2026-07-22T22:26:28Z","subjects":["Operations Research"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3153425"],"render_values":[{"text":"(MiAaPQ)AAI3153425","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/86845","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Diego Klabjan"]},{"key":"dc:creator","label":"Author","values":["Shebalov, Sergey"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-28T15:19:49Z","10000-01-01","2004"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Operations Research"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/86845","(MiAaPQ)AAI3153425"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We investigate the convex hull of the set defined by a single constraint with continues and binary variables and in addition, variable upper bound constraints are present. We introduce the flow cover inequality, which is valid for a projection. We also give conditions under which this inequality is facet defining. We use sequence independent lifting to obtain valid inequalities for the entire set. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. In the second part of the thesis we first elaborate on general sequence dependent lifting for this set and present a dynamic program for calculating lifting coefficients. Then we consider projections of this set to knapsack cover and to the single binary variable polytope. We present the result of sequence independent lifting of the knapsack cover inequality and obtain lifting some coefficients for sequence dependent lifting with for specific sequences. We generate two new families of facet defining inequalities for the single binary variable polytope and prove that combined with the trivial inequalities they give a full description of this polytope. Finally, we give an optimization problem for the lifting coefficients.","Made available in DSpace on 2015-09-28T15:19:49Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3153425.pdf: 4017108 bytes, checksum: 4c7130aba5c962a9f85ecf0381402f66 (MD5) Previous issue date: 2004","Embargo set by: Seth Robbins for item 88126 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","112 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2004."]},{"key":"dc:title","label":"Title","values":["Polyhedra Study of Mixed Integer Programs With Variable Upper Bounds"]}]}],"canonical_facts":{"dc:contributor":["Diego Klabjan"],"dc:creator":["Shebalov, Sergey"],"dc:date":["2015-09-28T15:19:49Z","10000-01-01","2004"],"dc:description":["We investigate the convex hull of the set defined by a single constraint with continues and binary variables and in addition, variable upper bound constraints are present. We introduce the flow cover inequality, which is valid for a projection. We also give conditions under which this inequality is facet defining. We use sequence independent lifting to obtain valid inequalities for the entire set. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. In the second part of the thesis we first elaborate on general sequence dependent lifting for this set and present a dynamic program for calculating lifting coefficients. Then we consider projections of this set to knapsack cover and to the single binary variable polytope. We present the result of sequence independent lifting of the knapsack cover inequality and obtain lifting some coefficients for sequence dependent lifting with for specific sequences. We generate two new families of facet defining inequalities for the single binary variable polytope and prove that combined with the trivial inequalities they give a full description of this polytope. Finally, we give an optimization problem for the lifting coefficients.","Made available in DSpace on 2015-09-28T15:19:49Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3153425.pdf: 4017108 bytes, checksum: 4c7130aba5c962a9f85ecf0381402f66 (MD5) Previous issue date: 2004","Embargo set by: Seth Robbins for item 88126 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","112 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2004."],"dc:identifier":["http://hdl.handle.net/2142/86845","(MiAaPQ)AAI3153425"],"dc:language":["eng"],"dc:subject":["Operations Research"],"dc:title":["Polyhedra Study of Mixed Integer Programs With Variable Upper Bounds"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:28Z"}