Solving a Mixed Integer Linear Program Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm
2014 (English)In: Transportmetrica A: Transport Science, ISSN 2324-9935 (Print), 2324-9943 (Online), Vol. 10, no 9, 791-819 p.Article in journal (Refereed) Published
This paper addresses the global optimality of the toll design problem (TDP) by a mixed integer linear program (MILP) approximation. In the TDP, the objective is to maximize the social surplus by adjusting toll locations and levels in a road traffic network. The resulting optimization problem can be formulated as a mathematical program with equilibrium constraints (MPEC).
A MILP is obtained by piecewise linear approximation of the non-linear functions in the TDP, and we present a domain reduction scheme to reduce the error introduced by these approximations. Previous approaches for solving the MILP approximation have been relying on a large number of MILPs to be solved iteratively within a cutting constraint algorithm (CCA). This paper instead focuses on the development of a solution algorithm for solving the MILP approximation in which the CCA is integrated within a branch and cut algorithm, which only requires one MILP to be solved.
Place, publisher, year, edition, pages
Taylor & Francis Group, 2014. Vol. 10, no 9, 791-819 p.
global optimisation; bilevel optimisation; toll design; road pricing
IdentifiersURN: urn:nbn:se:liu:diva-76642DOI: 10.1080/23249935.2013.813988ISI: 000340257500002OAI: oai:DiVA.org:liu-76642DiVA: diva2:515579
The original titel in manuscript form was Solving a MILP Approximation of the Toll Design Problem Using Constraint Generation within a Branch and Cut Algorithm.2012-04-132012-04-132014-10-23