Solving a mixed integer linear program approximation of the toll design problem using constraint generation within a branch-and-cut algorithm

This paper addresses the global optimality of the toll design problem (TDP) by formulating a mixed integer linear program (MILP) approximation. In the TDP, the objective is to maximise the social surplus by adjusting toll locations and levels in a road traffic network. The resulting optimisation problem can be formulated as a mathematical program with equilibrium constraints. An MILP is obtained by piecewise linear approximation of the nonlinear functions in the TDP, and the authors 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.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • © 2013 Hong Kong Society for Transportation Studies Limited 2013. Abstract reprinted with permission of Taylor & Francis.
  • Authors:
    • Ekström, Joakim
    • Rydergren, Clas
    • Sumalee, Agachai
  • Publication Date: 2014-10


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01530835
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jul 13 2014 3:00PM