Publication

A Lagrangian relaxation technique for the demand-based benefit maximization problem

Abstract

The integration of discrete choice models in Mixed Integer Linear Programming (MILP) models provides a better understanding of the preferences of the customers to the operators while planning for their systems. However, the formulations associated with choice models are highly nonlinear and non convex. In order to overcome this limitation, we propose a linear formulation of a general discrete choice model that can be embedded in any MILP formulation by relying on simulation. We characterize a demand-based benefit maximization problem to illustrate the use of this approach. Despite the clear advantages of this formulation, the size of the resulting problem is high, which makes it computationally expensive. Given its underlying structure, we consider Lagrangian relaxation to decompose it into two separable subproblems: one concerning the decisions of the operator and the other the choices of the customers. We can write the former as a Capacitated Facility Location Problem (CFLP), for which well-known solution methods can be used. We develop a tailored algorithm to solve the latter by assuming that the utility function is decreasing as a function of the price. We then define a subgradient method to optimize the problem on the Lagrangian multipliers (Lagrangian dual).

About this result
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 concepts (32)
Lagrange multiplier
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equation constraints (i.e., subject to the condition that one or more equations have to be satisfied exactly by the chosen values of the variables). It is named after the mathematician Joseph-Louis Lagrange. The basic idea is to convert a constrained problem into a form such that the derivative test of an unconstrained problem can still be applied.
Cutting-plane method
In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.
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.
Show more
Related publications (37)

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

Michel Bierlaire

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 de ...
2023

Solving stochastic weak Minty variational inequalities without increasing batch size

Volkan Cevher, Thomas Michaelsen Pethick

This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, ...
2023

Integrating advanced discrete choice models in mixed integer linear optimization

Michel Bierlaire, Bernard Gendron

In many transportation systems, a mismatch between the associated design and planning decisions and the demand is typically encountered. A tailored system is not only appealing to operators, which could have a better knowledge of their operational costs, b ...
PERGAMON-ELSEVIER SCIENCE LTD2021
Show more
Related MOOCs (10)
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.
Optimization: principles and algorithms - Network and discrete optimization
Introduction to network optimization and discrete optimization
Show more