<?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-22T13:16:53Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/19481" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/19481</identifier><datestamp>2025-03-26T23:37:30Z</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">Tunçel, Levent</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="c6d1ba52-3531-4fe1-851d-03cc6592e190" confidence="600">Lawrence, Paul</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2023-05-25T12:50:16Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2023-05-25T12:50:16Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2023-05-25</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2023-05-18</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/19481</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">A common topic of study in the subfield of Operations Research known as Revenue Management&#xd;
is finding optimal prices for a line of products given customer preferences. While there exists a&#xd;
large number of ways to model optimal pricing problems, in this thesis we study a price-based&#xd;
Revenue Management model known as the Maximum Utility Problem (MUP). In this model, we&#xd;
are given a set of n customer segments and m products, as well as reservation prices Rij which&#xd;
reflect the amount that Segment i is willing to pay for Product j. Using a number of structural and&#xd;
behavioral assumptions, if we derive a vector of prices for our line of products, we can compute an&#xd;
assignment of customers to products. We wish to find the set of prices that leads to the optimal&#xd;
amount of revenue given our rules for assigning customers to products. Using this framework, we&#xd;
can formulate a Nonlinear Mixed Integer Programming formulation that, while difficult to solve,&#xd;
has a surprising amount of underlying structure. If we fix an assignment and simply ask for the&#xd;
optimal set of prices such that said assignment is feasible, we obtain a new linear program, the&#xd;
dual of which happens to be a set of shortest-paths problems. This fact lead to the development of&#xd;
the Dobson-Kalish Algorithm, which explores a large number of assignments and quickly computes&#xd;
their optimal prices.&#xd;
&#xd;
Since the introduction of the Dobson-Kalish Algorithm, there has been a rich variety of literature&#xd;
surrounding MUP and its relatives. These include the introduction of utility tolerances to increase&#xd;
the robustness of the model, as well as new approximation algorithms, hardness results, and insights&#xd;
into the underlying combinatorial structure of the problem. After detailing this history, this thesis&#xd;
discusses a range of settings under which MUP can be solved in polynomial time. Relating it to&#xd;
other equilibria and price-based optimization problems, we overview Stackelberg Network Pricing&#xd;
Games as well as the general formulations of Bilevel Mixed Integer Linear Programs and Bilinear&#xd;
Mixed Integer Programs, showing that our formulation of the latter is in fact a more general version&#xd;
of the former. We provide some new structured instances for which we can prove additional ap-&#xd;
proximation and runtime results for existing algorithms. We also contribute a generalized heuristic&#xd;
algorithm and show that MUP can be solved exactly when the matrix of reservation prices is rank&#xd;
1. Finally, we discuss techniques for improving the upper bound to the overall problem, analyzing&#xd;
the primal and dual of the linear programming relaxation of MUP. To test the effectiveness of our&#xd;
approach, we analyze numerous examples that have been solved using Gurobi and present possible&#xd;
avenues for improving our ideas.</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">Algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Pricing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">linear programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">revenue</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">economic equilibria</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">approximation algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Algorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master 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">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Tunçel, 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>