EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
676. Fast Algorithms for Capacitated Continuous Pricing with Discrete Choice Demand Models
Invited abstract in session MD-59: Customer behaviour, stream Pricing and Revenue Management.
Monday, 14:30-16:00Room: S08 (building: 101)
Authors (first author is the speaker)
| 1. | Tom Haering
|
| School of Architecture, Civil and Environmental Engineering, EPFL | |
| 2. | Fabian Torres
|
| EPFL ENAC IIC TRANSP-OR | |
| 3. | Michel Bierlaire
|
| ENAC INTER TRANSP-OR, École Polytechnique Fédérale de Lausanne (EPFL) |
Abstract
This research introduces the Breakpoint Exact Algorithm with Capacities (BEAC) and the Breakpoint Heuristic Algorithm (BHA), both of which offer substantial advancements in solving the choice-based pricing problem (CPP) with and without capacity constraints. The BEAC, enhancing the Breakpoint Exact Algorithm (BEA) with a capacity management strategy, outperforms the state-of-the-art mixed-integer linear programming (MILP) approach by 20 times in computational speed. The BHA, employing a coordinate descent method, excels in high-dimensional scenarios, showing remarkable efficiency in both capacitated and uncapacitated cases. Notably, it outpaces the MILP by a factor of 100 to 5000 for the capacitated case, and the state-of-the-art Branch and Benders Decomposition approach by several orders of magnitude for the uncapacitated case, while maintaining an average optimality gap of less than 0.2%. The dynamic line search extension of the BHA succeeds in identifying the global optimum in all tested instances, albeit with a significant speed reduction. For future research, other extensions of the BHA to escape local optima should be considered.
Keywords
- Behavioural OR
- Algorithms
- Revenue Management and Pricing
Status: accepted
Back to the list of papers