Approximation algorithms for regret-bounded vehicle routing ...

Approximation algorithms for regret-bounded vehicle routing ...

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.

Recently Viewed Presentations

  • Review of exponential charging and discharging in RC Circuits

    Review of exponential charging and discharging in RC Circuits

    The op-amp can be modeled using the following circuit: You can simply replace the op-amp symbol with the above circuit for analysis. However, the above model is only valid when VO is within a certain range. Rails and Saturation The...
  • PowerPoint Lesson 3 Working with Visual Elements

    PowerPoint Lesson 3 Working with Visual Elements

    Working with SmartArt Graphics (continued) You can type text directly in the graphic or you can open the Text pane to the left of the SmartArt graphic to enter the text. You can format the text boxes. To go back...
  • Strategies to teach Writing to ESOL students

    Strategies to teach Writing to ESOL students

    • words, chunks of language, or simple phrasal patterns associated with common social and instructional situations • possible use of some conventions • usage of highest frequency general content related words • usage of everyday social and instructional words and...
  • About Plagiarism - Franklin University

    About Plagiarism - Franklin University

    Looks good, less work, but no learning * COMP 655 * Academic integrity - 2 Plagiarism is a problem: Several academic dishonesty charges have occurred during the past Students have been dismissed Some solutions: www.turnitin.com Turnitin setup information (COMP 655)...
  • Diapositive 0 - apigq.qc.ca

    Diapositive 0 - apigq.qc.ca

    Association professionnelle des ingénieurs du Gouvernement du Québec Le droit de surveillance de l'employeur et l'utilisation des réseaux sociaux : le juste équilibre entre la protection des droits du salarié et le droit de gérance de l'employeur
  • Chemistry: Atoms First Julia Burdge & Jason Overby

    Chemistry: Atoms First Julia Burdge & Jason Overby

    Ans: 32.17 °C Bomb Calorimetry and DH Bomb calorimetry can be used to determine the Heat of Reaction (DHrxn) the Heat of formation (DHf) and the Heat of solution (DHsoln) Q of the surroundings is equal to the total mass...
  • E3: Innate and Learned Behaviour - Ms De Souza's Super ...

    E3: Innate and Learned Behaviour - Ms De Souza's Super ...

    Kinesis. Stimuli: gas levels, humidity, air pressure, ambient temperature…. The rate of movement of the animal depends on the intensity of the stimuli and not it's directional. Ex: Woodlice are know to show kinesis to humidity. They dry out if...
  • Quick Review: What happened to Europe after the fall of the ...

    Quick Review: What happened to Europe after the fall of the ...

    Also known as the "Dark Ages" or "Medieval" era . ... Different dialects developed as new words and phrases became part of everyday speech. By the 800s, French, Spanish, and other Roman-based languages had evolved from Latin. ... Quick Review:...