Search Results

Documents authored by Coniglio, Stefano

Document
DOI: 10.4230/LIPIcs.SEA.2017.29
On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem

Authors: Stefano Coniglio and Stefano Gualandi

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
In the context of finding the largest stable set of a graph, rank inequalities prescribe that a stable set can contain, from any induced subgraph of the original graph, at most as many vertices as the stability number of the former. Although these inequalities subsume many of the valid inequalities known for the problem, their exact separation has only been investigated in few special cases obtained by restricting the induced subgraph to a specific topology. In this work, we propose a different approach in which, rather than imposing topological restrictions on the induced subgraph, we assume the right-hand side of the inequality to be fixed to a given (but arbitrary) constant. We then study the arising separation problem, which corresponds to the problem of finding a maximum weight subgraph with a bounded stability number. After proving its hardness and giving some insights on its polyhedral structure, we propose an exact branch-and-cut method for its solution. Computational results show that the separation of topology-free rank inequalities with a fixed right-hand side yields a substantial improvement over the bound provided by the fractional clique polytope (which is obtained with rank inequalities where the induced subgraph is restricted to a clique), often better than that obtained with Lovász’s Theta function via semidefinite programming.
Cite as

Stefano Coniglio and Stefano Gualandi. On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{coniglio_et_al:LIPIcs.SEA.2017.29,
  author =	{Coniglio, Stefano and Gualandi, Stefano},
  title =	{{On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.29},
  URN =		{urn:nbn:de:0030-drops-76266},
  doi =		{10.4230/LIPIcs.SEA.2017.29},
  annote =	{Keywords: Maximum stable set problem, rank inequalities, cutting planes, integer programming, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.31
Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria

Authors: Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We study the problem of computing an equilibrium in leader-follower games with a single leader and multiple followers where, after the leader’s commitment to a mixed strategy, the followers play simultaneously in a noncooperative way, reaching a Nash equilibrium. We tackle the problem from a bilevel programming perspective. Since, given the leader’s strategy, the followers’ subgame may admit multiple Nash equilibria, we consider the cases where the followers play either the best (optimistic) or the worst (pessimistic) Nash equilibrium in terms of the leader’s utility. For the optimistic case, we propose three formulations which cast the problem into a single level mixed-integer nonconvex program. For the pessimistic case, which, as we show, may admit a supremum but not a maximum, we develop an ad hoc branch-and-bound algorithm. Computational results are reported and illustrated.
Cite as

Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{basilico_et_al:LIPIcs.SEA.2017.31,
  author =	{Basilico, Nicola and Coniglio, Stefano and Gatti, Nicola and Marchesi, Alberto},
  title =	{{Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.31},
  URN =		{urn:nbn:de:0030-drops-76249},
  doi =		{10.4230/LIPIcs.SEA.2017.31},
  annote =	{Keywords: Stackelberg games; Nash equilibria; Game theory; Bilevel and nonlinear programming; Branch-and-bound}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact