BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Siqian Shen (University of Michigan) DTSTART:20210525T181500Z DTEND:20210525T184500Z DTSTAMP:20260417T110940Z UID:MIP2021/11 DESCRIPTION:Title: Sequential Competitive Facility Location: Exact and Approximate Algorithm s\nby Siqian Shen (University of Michigan) as part of Mixed Integer Pr ogramming Workshop 2021\n\n\nAbstract\nWe study a competitive facility loc ation problem (CFLP)\, in which two firms sequentially select locations of new facilities\, in order to maximize their market shares of customer dem and that follows a probabilistic choice model. This process is a Stackelbe rg game and admits a bilevel mixed-integer nonlinear program (MINLP) formu lation. Through integer programming methods\, we derive an equivalent\, si ngle-level MINLP reformulation. In addition\, we exploit the problem struc tures and derive two classes of valid inequalities\, one based on submodul arity and the other based on concave overestimation. We apply these inequa lities in a branch-and-cut algorithm to find a globally optimal solution t o CFLP. Furthermore\, we propose an approximation algorithm for solving CF LP that is computationally more effective. Notably\, this algorithm admits a constant approximation guarantee. Extensive numerical studies demonstra te that the exact algorithm can significantly accelerate the solving of CF LP on problem instances that have not been solved to optimality by existin g methods. The approximation algorithm can find near-optimal solutions eve n more quickly.\n\nThis is joint work with Mingyao Qi (Tsinghua U) and Rui wei Jiang (U of Michigan).\n LOCATION:https://researchseminars.org/talk/MIP2021/11/ END:VEVENT END:VCALENDAR