You are given the road network connecting the source A to the destination B, as in Fig.1. There are two numbers associated to each edge (road): the first one represents the traveling time while the second one is the toll fee (in $). You have a budget of 44$ and you want to go from A to B as fast as possible (minimum overall traveling time).

(a). (22 points) Formulate an integer LP that finds the most convenient path (i.e., the fastest path, subject to your budget constraint).

A 3,16 4,20 2,30 3 2.5,13 2.11 1.5, 25 2,8 4,14 6,23 Figure 1: Road network - Problem 3. B