Bortolomiol, S., Lurkin, V., and Bierlaire, M. (2021)

Benders decomposition for choice-based optimization problems with discrete upper-level variables

21st Swiss Transport Research Conference, ,

In this work, we consider a class of choice-based optimization problems in which the decision variables of the supplier are discrete. First, we compare this class of problems with a more general formulation which admits both continuous and discrete variables. A feasible solution of the problem with both continuous and discrete upper-level variables can be found by solving a problem with only discrete variables by discretizing all continuous variables of the original formulation. An appropriate discretization of all continuous variables can guarantee a good approximation of the solution of the original problem. A computational analysis shows that the discrete formulation is faster than the continuous-discrete formulation for complex problems. Then, we show that in the discrete formulation, in which all utility functions of the customers can be expressed as parameters of the supplier's optimization problem, the lower-level optimization problem of the customer is a continuous knapsack problem. This property is used to derive a Benders decomposition algorithm for the choice-based optimization problem with discrete variables.