<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T18:20:59Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/18178" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/18178</identifier><datestamp>2025-03-26T23:33:47Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Guenin, Bertrand</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Tuncel, Levent</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="b52ac2ac-339b-49d7-af51-8880f32a6ca8" confidence="600">Stuive, Leanne</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2022-04-26T17:18:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2022-04-26T17:18:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2022-04-26</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2022-04-14</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/18178</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Mixed integer programs are a powerful mathematical tool, providing a general model for expressing both theoretically difficult and practically useful problems. One important subroutine of algorithms solving mixed integer programs is a cut generation procedure. The job of a cut generation procedure is to produce a linear inequality that separates a given infeasible point x* (usually a basic feasible solution of the linear programming relaxation) from the set of feasible solutions for the problem at hand. Early and well-known cut generation procedures rely on analyzing a single row of the simplex tableau for x*. Andersen et al. renewed interest in d-row cuts (i.e. cuts derived from d rows of the simplex tableau) by showing that these cuts afford some theoretical benefit.&#xd;
&#xd;
One lens from which to study d-row cuts is in the context of the intersection cuts of Balas and, in particular, intersection cuts obtained from lattice-free convex sets. The strongest d-row intersection cuts are obtained from maximal lattice-free convex sets in $R^d$ - all of which are polyhedra with at most $2^d$ facets. This thesis is concerned with theoretical comparison of the d-row cuts generated by different families of maximal lattice-free convex sets. We use the gauge measure to appraise the quality of the approximation. The main area of focus is 2-row cuts.&#xd;
&#xd;
The problem of generating 2-row cuts can be re-posed as generating valid inequalities for a mixed integer linear set F with two free integer variables and any number of non-negative continuous variables, where there are two defining equations. Every minimal valid inequality for the convex hull of F is an intersection cut generated by a maximal lattice-free split, triangle or quadrilateral. The family of maximal lattice-free triangles can be subdivided into the families of type 1, type 2, and type 3 triangles.&#xd;
&#xd;
Previous results of Basu et al. and Awate et al. compare how well the inequalities from one of these families approximates the convex hull of F (a.k.a. the corner polyhedron). In particular, the closure of all type 2 triangle inequalities is shown to be within a factor of 3/2 of the corner polyhedron. The authors also provide an instance where all type 2 triangles inequalities cannot approximate the corner polyhedron better than a factor of 9/8. The same bounds are shown for type 3 triangles and quadrilaterals. These results are obtained not by directly comparing the given closures to the convex hull of F, but rather to each other.&#xd;
&#xd;
In this thesis, we tighten one of the underlying bounds, showing that the closure of all type 2 triangle inequalities are within a factor of 5/4 of the closure of all quadrilateral inequalities. We also consider the sub-family of quadrilaterals where opposite edges have equal slope. We show that these parallelogram cuts can be approximated by all type 2 triangle inequalities within a factor of 9/8 and there exist instances where no better approximation is possible. In proving both these bounds, we use a subset of the family of type 2 triangles; we call the members of this sub-family ray-sliding triangles.&#xd;
&#xd;
A secondary area of focus in this thesis is d-row cuts for d &amp;gt;= 3. For d-row cuts in general, the underlying maximal lattice-free convex sets in $R^d$ are not easily classified. Absent a classification, Averkov et al, show that all inequalities generated by lattice-free convex sets with at most $i$ facets approximate the corner polyhedron within a finite factor only when $i &amp;gt; 2^{d-1}$. Here we take a different tact and try to prove analogues of 2-row cut results.  We extend the proof techniques to obtain a constant factor approximation between two structured families of maximal lattice-free convex sets in $R^d$ for d &amp;gt;= 3.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">integer programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">mathematical optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">intersection cuts</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">multi-row models</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Comparing Intersection Cut Closures using Simple Families of Lattice-Free Convex Sets</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Guenin, Bertrand</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Tuncel, Levent</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>