Algorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem
Bibliographic record
Abstract
A common topic of study in the subfield of Operations Research known as Revenue Management \nis finding optimal prices for a line of products given customer preferences. While there exists a \nlarge number of ways to model optimal pricing problems, in this thesis we study a price-based \nRevenue Management model known as the Maximum Utility Problem (MUP). In this model, we \nare given a set of n customer segments and m products, as well as reservation prices Rij which \nreflect the amount that Segment i is willing to pay for Product j. Using a number of structural and \nbehavioral assumptions, if we derive a vector of prices for our line of products, we can compute an \nassignment of customers to products. We wish to find the set of prices that leads to the optimal \namount of revenue given our rules for assigning customers to products. Using this framework, we \ncan formulate a Nonlinear Mixed Integer Programming formulation that, while difficult to solve, \nhas a surprising amount of underlying structure. If we fix an assignment and simply ask for the \noptimal set of prices such that said assignment is feasible, we obtain a new linear program, the \ndual of which happens to be a set of shortest-paths problems. This fact lead to the development of \nthe Dobson-Kalish Algorithm, which explores a large number of assignments and quickly computes \ntheir optimal prices. \n \nSince the introduction of the Dobson-Kalish Algorithm, there has been a rich variety of literature \nsurrounding MUP and its relatives. These include the introduction of utility tolerances to increase \nthe robustness of the model, as well as new approximation algorithms, hardness results, and insights \ninto the underlying combinatorial structure of the problem. After detailing this history, this thesis \ndiscusses a range of settings under which MUP can be solved in polynomial time. Relating it to \nother equilibria and price-based optimization problems, we overview Stackelberg Network Pricing \nGames as well as the general formulations of Bilevel Mixed Integer Linear Programs and Bilinear \nMixed Integer Programs, showing that our formulation of the latter is in fact a more general version \nof the former. We provide some new structured instances for which we can prove additional ap- \nproximation and runtime results for existing algorithms. We also contribute a generalized heuristic \nalgorithm and show that MUP can be solved exactly when the matrix of reservation prices is rank \n1. Finally, we discuss techniques for improving the upper bound to the overall problem, analyzing \nthe primal and dual of the linear programming relaxation of MUP. To test the effectiveness of our \napproach, we analyze numerous examples that have been solved using Gurobi and present possible \navenues for improving our ideas.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.004 | 0.013 |
| Meta-epidemiology (narrow) | 0.003 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.003 |
| Bibliometrics | 0.002 | 0.004 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.003 | 0.005 |
| Open science | 0.003 | 0.003 |
| Research integrity | 0.002 | 0.009 |
| Insufficient payload (model declined to judge) | 0.012 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".