- Mathematical programming approaches to pricing problems
- Violin, Alessia
Subject
- combinatorial optimization
- tolls
- Dantzig-Wolfe
- mixed-integer programming
- bilevel programming
- column generation
- Branch-and-Price
- SCIP
- pricing
- ottimizzazione combinatoria
- programmazione mista intera
- generazione di colonne
- tariffazione
- pedaggi
- programmazione bilivello
- optimisation combinatoire
- programmation mixte entière
- programmation biniveau
- tarification
- péages
- génération de colonnes
- SCUOLA DI DOTTORATO DI RICERCA IN INGEGNERIA DELL'INFORMAZIONE
- MAT/09 RICERCA OPERATIVA
Description
- 2012/2013
- There are many real cases where a company needs to determine the price of its products so as to maximise its revenue or profit. To do so, the company must consider customers’ reactions to these prices, as they may refuse to buy a given product or service if its price is too high. This is commonly known in literature as a pricing problem. This class of problems, which is typically bilevel, was first studied in the 1990s and is NP-hard, although polynomial algorithms do exist for some particular cases. Many questions are still open on this subject. The aim of this thesis is to investigate mathematical properties of pricing problems, in order to find structural properties, formulations and solution methods that are as efficient as possible. In particular, we focus our attention on pricing problems over a network. In this framework, an authority owns a subset of arcs and imposes tolls on them, in an attempt to maximise his/her revenue, while users travel on the network, seeking for their minimum cost path. First, we provide a detailed review of the state of the art on bilevel pricing problems. Then, we consider a particular case where the authority is using an unit toll scheme on his/her subset of arcs, imposing either the same toll on all of them, or a toll proportional to a given parameter particular to each arc (for instance a per kilometre toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial. We then address a robust approach taking into account uncertainty on parameters. We solve some polynomial cases of the pricing problem where uncertainty is considered using an interval representation. Finally, we focus on another particular case where toll arcs are connected such that they constitute a path, as occurs on highways. We develop a Dantzig-Wolfe reformulation and present a Branch-and-Cut-and-Price algorithm to solve it. Several improvements are proposed, both for the column generation algorithm used to solve the linear relaxation and for the branching part used to find integer solutions. Numerical results are also presented to highlight the efficiency of the proposed strategies. This problem is proved to be APX-hard and a theoretical comparison between our model and another one from the literature is carried out.
- Un problème classique pour une compagnie est la tarification de ses produits à vendre sur le marché, de façon à maximiser les revenus. Dans ce contexte, il est important que la société prenne en compte le comportement de ses clients potentiels, puisque si le prix est trop élevé, ils peuvent décider de ne rien acheter. Ce problème est communément connu dans la littérature comme un problème de tarification ou "pricing". Une approche de programmation biniveau pour ce problème a été introduite dans les années 90, révélant sa difficulté. Cependant, certains cas particuliers peuvent être résolus par des algorithmes polynomiaux, et il y a encore de nombreuses questions ouvertes sur le sujet. Cette thèse de doctorat porte sur les propriétés mathématiques des problèmes de tarification, fixant l’objectif de déterminer différentes formulations et méthodes de résolution les plus efficaces possibles, en se concentrant sur les problèmes appliqués aux réseaux de différents types. Dans les problèmes de tarification sur réseau, nous avons deux entités : une autorité qui possède un certain sous-ensemble d’arcs, et impose des péages, avec l’intention de maximiser les revenus provenant de celle-ci, et des utilisateurs qui choisissent leur chemin de moindre coût sur l’ensemble du réseau. Dans la première partie de la thèse une analyse détaillée de l’état de l’art sur les problèmes de tarification biniveau est présentée, suivie, dans la deuxième partie, par une analyse de cas particuliers polynomiaux. En particulier, nous considérons le cas où l’autorité utilise un péage unitaire sur son sous-ensemble d’arcs, soit en choisissant le même péage sur chaque arc, soit en choisissant un péage proportionnel à un paramètre donné pour chaque arc (par exemple, un péage par kilomètre). Dans le premier cas de péages égaux, il est démontré que la complexité du problème est polynomiale, tandis que dans le second cas de péages proportionnels, elle est pseudo-polynomiale. Ensuite, nous présentons une première approche d’optimisation robuste pour les problèmes de tarification sur réseau, de manière à inclure de l’incertitude sur la valeur exacte des paramètres dans le modèle, qui est typique dans les problèmes réels. Cette incertitude est représentée en utilisant des intervalles pour les paramètres et nous proposons, pour certains cas, des algorithmes de résolution polynomiaux. La troisième et dernière partie de la thèse concerne un cas difficile, le problème de tarification sur réseau dans lequel les arcs sont connectés de manière à constituer un chemin, comme c’est le cas pour les autoroutes. Initialement, nous prouvons que ce problème est APX-dur, renforçant le résultat connu jusqu’à maintenant. Ensuite, nous présentons des nouvelles formulations plus fortes, et en particulier, nous développons une reformulation de type Danztig-Wolfe, résolue par un algorithme de Branch-and-Cut-and-Price. Enfin, nous proposons différentes stratégies pour améliorer les performances de l’algorithme, pour ce qui concerne l’algorithme de génération de colonnes utilisé pour résoudre la relaxation linéaire, et pour ce qui concerne la résolution du problème avec variables binaires. Les résultats numériques complètent les résultats théoriques, en mettant en évidence l’efficacité des stratégies proposées.
- Un classico problema aziendale è la determinazione del prezzo dei prodotti da vendere sul mercato, in modo tale da massimizzare le entrate che ne deriveranno. In tale contesto è importante che l’azienda tenga in considerazione il comportamento dei propri potenziali clienti, in quanto questi ultimi potrebbero ritenere che il prezzo sia troppo alto e decidere dunque di non acquistare. Questo problema è comunemente noto in letteratura come problema di tariffazione o di “pricing”. Tale problema è stato studiato negli anni novanta mediante un approccio bilivello, rivelandone l’alta complessità computazionale. Tuttavia alcuni casi particolari possono essere risolti mediante algoritmi polinomiali, e ci sono sono ancora molte domande aperte sull’argomento. Questa tesi di dottorato si focalizza sulle proprietà matematiche dei problemi di tariffazione, ponendosi l’obiettivo di determinarne formulazioni e metodi risolutivi più efficienti possibili, concentrandosi sui problemi applicati a reti di vario tipo. Nei problemi di tariffazione su rete si hanno due entità: un’autorità che possiede un certo sottoinsieme di archi e vi impone dei pedaggi, con l’intento di massimizzare le entrate che ne derivano, e gli utenti che scelgono il proprio percorso a costo minimo sulla rete complessiva (a pedaggio e non). Nella prima parte della tesi viene affrontata una dettagliata analisi dello stato dell’arte sui problemi di tariffazione bilivello, seguita, nella seconda parte, dall’analisi di particolari casi polinomiali del problema. In particolare si considera il caso in cui l’autorità utilizza uno schema di pedaggio unitario sul suo sottoinsieme di archi, imponendo o lo stesso pedaggio su ogni arco, o un pedaggio proporzionale a un dato parametro relativo ad ogni arco (ad esempio un pedaggio al chilometro). Nel primo caso di pedaggi uguali, si dimostra che la complessità del problema è polinomiale, mentre nel secondo caso di pedaggi proporzionali è pseudo-polinomiale. In seguito viene affrontato un approccio di ottimizzazione robusta per alcuni problemi di tariffazione su rete, in modo da includere nei modelli un’incertezza sul valore esatto dei parametri,tipica dei problemi reali. Tale incertezza viene rappresentata vincolando i parametri in degli intervalli e si propongono, per alcuni casi, algoritmi risolutivi polinomiali. La terza e ultima parte della tesi riguarda un caso computazionalmente difficile, in cui gli archi tariffabili sono connessi in modo tale da costituire un cammino, come avviene per le autostrade. Inizialmente si dimostra che tale problema è APX-hard, rafforzando il risultato finora conosciuto. In seguito si considerano formulazioni piùforti, e in particolare si sviluppa una riformulazione di Danztig-Wolfe, risolta tramite un algoritmo di Branch-and-Cut-and-Price. Infine si propongono diverse strategie per migliorare le performance dell’algoritmo, sia per quanto riguarda l’algoritmo di generazione di colonne utilizzato per risolvere il rilassamento lineare, sia per quanto riguarda la risoluzione del problema con variabili binarie. Risultati numerici complementano quelli teorici ed evidenziano l’efficacia delle strategie proposte.
- XXV Ciclo
- 1985
Date
- 2015-03-17T11:13:01Z
- 2015-03-17T11:13:01Z
- 2014-12-18
Type
- Doctoral Thesis
Format
- application/pdf
Identifier
urn:nbn:it:units-13683