Lecture notes 2: ApplicationsVincent ConitzerIn this set of notes, we will discuss a number of problems of interest to computer scientists wherelinear/integer programming can be fruitfully applied.1 Maximum flowIn the maximum flow problem, we are given a directed graph with a distinguished source node anda distinguished sink node. In addition, each edge has a capacity, which is the largest amount of flowthat can go over this edge. Our goal is to route as much flow from the source to the sink as we can,along the edges of the graph. For example, consider the directed graph with capacities in Figure 1,where S is the source and T is the sink.SABCT5224376Figure 1: An instance of the maximum flow problem.1The maximum flow that can be sent from S to T is 7, by sending 3 units from S to A; 4 from Sto C; 3 from A to B ; 0 from A to C; 2 from C to B; 5 from B to T ; and 2 from C to T . Note thatevery node other than S and T receives exactly as much flow as it sends (since these nodes cannot“produce” flow).We can model the maximum flow problem as a linear program as follows. For any nodes v andw, let fv w(a variable) be the flow from v to w. We must have fv w≤ cv w, where cv w(a parameter)is the capacity of edge (v, w). (For pairs v, w without an edge from v to w, we can either not havea flow variable fv wat all, or we can say cv w= 0.) In addition, we have a constraint that for anynode v /∈ {s, t} (where s and t are the source and sink),Pufuv=Pwfv w—that is, the flow into vequals the flow out of v. Putting it all together, letting V be the set of vertices (nodes) and E theset of (directed) edges, we get:maximizePv ∈V :(v,t)∈Efv tsubject to(∀(v, w) ∈ E) fv w≤ cv w(∀v ∈ V − {s, t})Pu∈V :(u,v)∈Efuv−Pw∈V :(v,w)∈Efv w= 0(∀(v, w) ∈ E) fv w≥ 0As you can see , the way this linear program is written looks somewhat different from before: we areusing ∀s andPs, and we are not using xjfor the variables. Still, it is a linear program, and for anyinstance it can be converted to the standard way of writing linear programs that we saw before. Forexample, for the instance in Figure 1, the program becomes:maximize fBT+ fCTsubject tofSA≤ 3fSC≤ 5fAC≤ 6fAB≤ 4fCB≤ 2fBT≤ 7fCT≤ 2fSA− fAC− fAB= 0fSC+ fAC− fCB− fCT= 0fAB+ fCB− fBT= 0fSA≥ 0, fSC≥ 0, fAC≥ 0, fAB≥ 0, fCB≥ 0, fBT≥ 0, fCT≥ 0It is generally helpful to allow some flexibility in how we write linear programs, especially when wewrite them in an abstract form; but it is important to stay aware of the distinction between variablesand parameters.The fact that we can model the maximum flow problem as a (polynomial-size) linear programimmediately implies that the maximum flow problem can be solved in polynomial time, because linearprograms can be solved in polynomial time. There are specialized algorithms for the maximum flowproblem that are more efficient than solving it as a linear program. Nevertheless, modeling it asa linear program is quick and simple. It is also a very flexible approach that is easily modified tovariants of the problem. Finally, we will see later that we can prove some basic properties of themaximum flow problem using this linear program formulation.22 Combinatorial auctionsImagine that you are in the following situation. On an online auction site, you have found someoneselling a desktop computer that you like. Unfortunately, it does not come with a monitor. However,you have found another seller, on the same website, who is selling a monitor that you like. If youwere to win both items, this would be worth $500 to you. However, if you win only the desktopcomputer, or only the monitor, this would be worth nothing to you at all. (For simplicity, let usassume that you cannot buy a des ktop or monitor anywhere else.) Now, you are about to go onvacation, so for each auction, you must specify how high you are willing to bid. (Auction websitesoften ask you to specify this, and will then automatically bid up to the price that you stated.) Howhigh should you be willing to bid in each auction? If you say you are willing to go up to, say, $250in each auction, you run the risk of winning one of them but not the other, resulting in a loss of upto $250 in total for you. In fact, regardless of what you say, you may end up with a loss—unlessyou say $0 on both items. What you would like to do is to specify that you are willing to pay upto $500 on the bundle of both the desktop and the monitor. This is what a combinatorial auctionwould allow you to do. Such auctions are becoming more common.In a combinatorial auction, there is a set of items I which are simultaneously for sale, and biddersplace bids on bundles. For example, if I = {A, B, C, D}, a bid might be ({A, C, D}, 5), indicatingthat this bidder is willing to pay 5 for receiving all of the items A, C, and D. In a sealed-bidcombinatorial auction, all of these bids are submitted simultaneously. Once we have received all thebids, we are faced with the winner determination problem of deciding which of these bids win. Wecan award each item at most once, so we cannot accept two bids if they have one or more items incommon. Under this constraint, generally, the goal is to accept bids in a way that maximizes thesum of the values of the accepted bids.For example, supp ose that there are 4 items, A, B, C, D, and that we receive the following bids:({A, B}, 4), ({B, C}, 5), ({A, C}, 4), ({A, B, D}, 7), ({D}, 1). It is easy to see that of the first 4 bids,we can accept at most 1, because every pair of the first 4 bids overlaps. Hence, the optimal solutionis to just accept ({A, B, D}, 7), and let C go unallocated, for a total value of 7. The second-bestfeasible solution is to accept ({B, C}, 5) and ({D}, 1), for a total value of 6.We can model the winner determination problem as an integer program as follows. For every bidb, let there be a variable xbthat take s values in {0, 1} (a binary variable); setting this variable to 1means that the bid is accepted, and setting it to 0 means that it is rejected. For each bid b and itemi, let there be a parameter aibwhich is 1 if item i is included in bid b, and 0 if it is not. Finally, letvbbe the value of bid b. Then we can write the winner determination problem as follows:maximizePbvbxbsubject to(∀i ∈ I)Pbaibxb≤ 1(∀b) xb∈ {0, 1}(Effectively, xb∈ {0, 1} is shorthand for xb≥ 0, xb≤ 1, and xbis an integer.)The winner determination problem is NP-hard, so we should not expect to