**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Abstract

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling demand on the level of individuals very accurately due to a focus on behavioral realism. The downside of such realistic models is that it is highly nontrivial to include the resulting demand probabilities into an optimization problem, as they usually do not have a convex or even closed-form expression when decision variables are part of the choice model. To this end, a simulation procedure proposed by Paneque et al. (2021) is applied to get a formulation as a mixed integer linear program (MILP). However, due to the large number of variables stemming from the simulation, this MILP is very hard to solve. We first propose to solve the problem as a non-convex quadratically constrained quadratic program (QCQP) instead, where total unimodularity guarantees the integrality of the solution. Isolating all non-convexity into a set of bilinear constraints leads to a formulation as a non-convex quadratically constrained linear program (QCLP) that proves computationally beneficial for general-purpose solvers. Lastly, we present a spatial branch and bound algorithm that employs the McCormick envelope to obtain relaxations and makes use of total unimodularity to generate feasible solutions and thus lower bounds for the maximization fast. We compare the proposed method to the fastest commercially available solver GUROBI, on a parking choice case study from Ibeas et al. (2014). The results show that the custom spatial branch and bound approach outspeeds GUROBI by a factor of at least 35x for the MILP formulation and at least 2.5x for the QCLP in single-price optimization, and a factor of at least 4.5x for the QCQP and 1.3x for the QCLP when optimizing multiple prices simultaneously. The ratio of the speedup further increases with the size of the instance.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related MOOCs (24)

Related publications (156)

Related concepts (35)

Selected Topics on Discrete Choice

Discrete choice models are used extensively in many disciplines where it is important to predict human behavior at a disaggregate level. This course is a follow up of the online course “Introduction t

Selected Topics on Discrete Choice

Discrete choice models are used extensively in many disciplines where it is important to predict human behavior at a disaggregate level. This course is a follow up of the online course “Introduction t

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Convex optimization

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

, ,

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024Ontological neighbourhood

In urban air mobility (UAM) networks, takeoff and landing sites, called vertiports, are likely to experience intermittent closures due to, e.g., adverse weather. To ensure safety, all in-flight urban air vehicles (UAVs) in a UAM network must therefore have ...

2024We develop a very general version of the hyperbola method which extends the known method by Blomer and Brudern for products of projective spaces to complete smooth split toric varieties. We use it to count Campana points of bounded log-anticanonical height ...