A single-level mixed integer linear formulation for a bi-level discrete network design problem

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. In this paper, a single-level mixed integer linear programming (SL-MILP) formulation for bi-level DNDP is presented. To cope with the dependency of node-link adjacency matrix on new links, travel time function is appropriately modified. The nonlinearity of the travel time function is also removed by means of a convex-combination based linear approximation which takes advantage of a unimodular structure. Two valid inequalities is developed which shorten computation time significantly. The validity of the proposed formulation is examined by two test problems. SL-MILP is able to provide optimal solution.

Research highlights
► An approximately equivalent single-level formulation for a bi-level discrete network design problem.
► An MILP formulation for discrete network design problem, handling side constraints.
► An efficient unimodular linear approximation scheme for nonlinear travel time function.