Algorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem
Notice bibliographique
Résumé
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.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,004 | 0,013 |
| Méta-épidémiologie (sens strict) | 0,003 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,003 |
| Bibliométrie | 0,002 | 0,004 |
| Études des sciences et des technologies | 0,001 | 0,002 |
| Communication savante | 0,003 | 0,005 |
| Science ouverte | 0,003 | 0,003 |
| Intégrité de la recherche | 0,002 | 0,009 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,012 | 0,002 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».