Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing Chaitanya Swamy University of Waterloo Joint work with Zachary Friggstad University of Alberta Orienteering 7 5 3 5 2 r Metric space root r 5

2 2 nodes with rewards ( 0)node p(v) v reward of v Orienteering 7 5 2 r p(P) = 24 3 5 P 2

Metric space 5 2 root r (p(r) = 0) nodes with rewards ( 0)node p(v) v reward of v length bound B Rooted orienteering: find r-rooted path P of length B that collects maximum reward p(P) := vP p(v) Point-to-point (P2P) orienteering: also given end-node t; find r-t path P of length B collecting max reward p(P) Orienteering is a basic vehicle-routing problem (VRP) Natural, well-motivated problem

Arises as a subroutine both in designing approximation algorithms for various VRPs: deadline TSP, minimumlatency problems computational methods for solving VRPs: pricing problem encountered in solving set-covering LPs configuration LPs via column-generation based approach Regret-bounded VRP (RVRP) r Metric space root r node/ client Typical VRP setup: visit all clients via route(s) starting from r so as to minimize client delays: e.g., max client delay (TSP) But this does not differentiate between clients close to the depot and those far away from it Nearer clients may face more delay than furtheraway clients source of dissatisfaction

Regret-bounded VRP (RVRP) r Metric space root r node/ client Adopt a more client-centric view: seek bounded client regret regret of client v = (waiting time of v) (shortest-path distance from r to v) Regret-bounded VRP (RVRP) c (v P ) r Dv v P

Metric space root r node/ client time to bounded reach v Adopt more client-centric cview: P(v) = ensure along client regret regret of client v =P (waiting time of v) (shortest-path distance from r to v) Dv (min. possible waiting time of v) RVRP: Given regret bound R, find minimum no. of r-rooted paths that cover all clients s.t. regret of every client R = For a rooted path P, let regret of P := regret of endnode of P c(P) Dend node of

P For a rooted path P, let regret of P := regret of endnode of P Let C(R) = {rooted paths P: regret of P R} Minimize xP 1 vV PC(R) xP (LP) s.t. PC(R): vP x0 (LP) is a set-cover LP can get O(log n)approximation using greedy algorithm for set cover greedy step (find path in C(R) covering max. # of new nodes) (P2P-) orienteering In fact, (LP) has O() integrality gap (Friggstad-S14) To approximately solve (LP) in polytime via ellipsoid, need to solve the dual; dual separation problem is again orienteering Our results Give natural, compact LP-relaxation for rooted orienteering + simple LP-rounding 3approximation algorithm First, LP-based guarantee for orienteering.

Our results Give natural, compact LP-relaxation for rooted orienteering + simple LP-rounding 3approximation algorithm First, LP-based guarantee for orienteering. All previous approaches (Blum et al., Bansal et al., Chekuri et al.) used dynamic programming (DP) to stitch together subpaths, which are found using another DP, or by solving a k-MST style problem. Our approach gives a clean, simple algorithm. Ideas may lead to compact, strong LPs for other problems that use orienteering (we show this for RVRP). LP-based insights are often versatile and adaptable to handle variants of the problem. DP-based approach gives (2+e)-approximation (Chekuri et al.); it is likely however that our 3-approximation guarantee is not tight. Our results Give natural, compact LP-relaxation for rooted orienteering + simple LP-rounding 3approximation algorithm First, LP-based guarantee for orienteering. Ideas may lead to compact, strong LPs for other problems that use orienteering (we show this for RVRP). Show that P2P-orienteering reduces to regretversion of rooted orienteering (length bound is replaced by regret bound) losing a factor of 2

No such reduction to a rooted problem was known: all previous approaches relied on approximations for P2Ppath problems LP for rooted orienteering extends to regret version get LP for P2P-orienteering with integrality gap 6 Our results (contd.) For RVRP, we propose two compact (i.e., poly-size) LP-relaxations with small integrality gaps yields15-approx. for First LP adapts RVRP orienteering-LP to RVRP Second LP is an unorthodox LP that exploits structural insights about an RVRP solution Both LPs have efficient LP-rounding algorithms: lead to improvements over previous-best O()-approx. for RVRP (FriggstadS14) (and substantial savings in running time) Compact LP for orienteering cu cu

graph Metric space complete Bidirect edges to get digraph uv v v (view rooted path as directed away from r) u cu v v Suppose we know node w on optimum path with w largest Dv r shortest-path distance from r to v

Compact LP for orienteering cu cu graph Metric space complete Bidirect edges to get digraph uv v v (view rooted path as directed away from r) u cu v v

Suppose we know node w on optimum path with largest Dv zwu : indicates if node u lies on path w x lieswon path a :indictes if arc Maximize ap(u)z u u subject to, xw(din(u)) xw(dout(u)) for all u r r w out w in x (d (r))

= , x (d (u)) = 0 for all u: Du S > Dw u a ca xwa B Compact LP for orienteering cu cu graph Metric space complete Bidirect edges to get digraph uv v

v (view rooted path as directed away from r) u cu v v Suppose we know node w on optimum path with largest Dv zwu : indicates if node u lies on path xw: r-preflow of value w x lieswon path(relaxation of rooted a :indictes if arc Maximize u ap(u)z u path) w

in w subject to, x (d (u)) x (dout(u)) for all u r r w out w in x (d (r)) = , x (d (u)) = 0 for all u: Du S > Dw u a ca xwa B

Compact LP for orienteering cu cu graph Metric space complete Bidirect edges to get digraph uv v v (view rooted path as directed away from r) u cu v v

Suppose we know node w on optimum path with largest Dv zwu : indicates if node u lies on path w x lieswon path a :indictes if arc Maximize ap(u)z u u outencoded by can be subject to, xw(din(u)) xw(d (u)) for all u r r polynomial # of flow w

out w inconstraints x (d (r)) = , x (d (u)) = 0 for all u: Du S > Dw u a ca xwa B Compact LP for orienteering Suppose we know node w on optimum path with largest Dv zwu : if node u lies on path,

w x path wu Maximize u p(u)z a :if arc a lies on (O-P) subject to, xw(din(u)) xw(dout(u)) for all u r xw(dout(r)) = , xw(din(u)) = 0 for all u: Du > Dw a c a xw a B w zw w rS, xw(din(S))zwu z Constraints ensure: u, all zS: u allfor w for

u = 0 if uS Du > Dw w z = ,knowing x, z w0. w for Can eliminate need (use zw to denote w Rounding algorithm Let (, ): optimal solution to (O-P), OPT = value of (, ) Key insight: can be viewed as an arborescence 0. packing 1w + 0.1 r 0.6 0.1 r

0.1 0.6 0.1 w 0.3 0.5 0.1 0.3 0.3 0.3 0. 3w 0. 3w r r + r

0. 3w + Rounding algorithm Let (, ): optimal solution to (O-P), OPT = value of (, ) Key insight: can be viewed as an arborescence packing Theorem (Bang-Jensen et al. 95): There are outarborescences T,,Tq rooted at r with weights such that: i = (total -weight of Tis containing arc a) for every arc a (total -weight of Tis containing node u) for every node u (Every Ti contains w;

nodes u with Du > Dw are not Rounding algorithm Let (, ): optimal solution to (O-P), OPT = value of (, ) Theorem (Bang-Jensen et al. 95): There are outarborescences T,,Tq rooted at r with weights , i = s.t. (total -weight of Tis containing arc a) for every arc a (total -weight of Tis containing node u) for every node u (Every Ti contains w; nodes u with Du > Dw are not in any Ti) Algorithm: 1) Obtain (Ti , ) pairs satisfying above properties. Rounding algorithm Let (, ): optimal solution to (O-P), (, ) OPT = value of Algorithm: 1) Obtain (Ti , ) pairs as in arborescence-packing theorem. (Every Ti contains w, nodes u with Du >

Dw are not in any Ti) 2) Convert every Ti to an r-w path Pi s.t. c(Pi) 2c(Ti) Dw So i .(regret of Pi) 2(B Dw), i .p(Pi) OPT 3) Path-splitting rlemma: a rooted path P of regret bR, can be split into at most (+b) rooted paths, each of regret R. Rounding algorithm Let (, ): optimal solution to (O-P), (, ) OPT = value of Algorithm: 1) Obtain (Ti , ) pairs as in arborescence-packing theorem. (Every Ti contains w, nodes u with Du > Dw are not in any Ti) 2) Convert every Ti to an r-w path Pi s.t. c(Pi) 2c(Ti) Dw So i .(regret of Pi) 2(B Dw), i .p(Pi) OPT 3) Path-splitting rlemma: a rooted path P of regret bR, can be split into at most (+b) rooted paths, each of regret R.

Rounding algorithm Let (, ): optimal solution to (O-P), (, ) OPT = value of Algorithm: 1) Obtain (Ti , ) pairs as in arborescence-packing theorem. (Every Ti contains w, nodes u with Du > Dw are not in any Ti) 2) Convert every Ti to an r-w path Pi s.t. c(Pi) 2c(Ti) Dw So i .(regret of Pi) 2(B Dw), i .p(Pi) OPT has length B 3) Path-splitting lemma: a rooted path P of regret bR, can be split into at most (+b) rooted paths, each of regret R. Apply path-splitting lemma with R = B Dw to each Conclusions and open questions Give compact LP-relaxations for orienteering and RVRP, devise LP-rounding algorithms for orienteering

and RVRP 3-approx. for rooted orienteering: first LP-based guarantee, simple rounding algorithm using arborescence packings Reduce P2P-orienteering to rooted regret-version of orienteering losing a factor of 2 Two compact LPs for RVRP, one of which leads to 15-approx. for RVRP Recent work: can solve prize-collecting version of (O-P) and obtain arborescences combinatorially (Post-S17) What is the integrality gap of (O-P)? Believe 2 is the right answer Better algorithms for 2 prominent generalizations of Thank You.