Connections in networks: hardness of feasibility versus optimality

Conrad, J.;Gomes, C.P.;van Hoeve, W.-J.;Sabharwal, A.;Suter, J.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Conrad, J.
    Author
  • Gomes, C.P.
    Author
  • van Hoeve, W.-J.
    Author
  • Sabharwal, A.
    Author
  • Suter, J.
    Author
Abstract
We study the complexity of combinatorial problems that consist of competing infeasibility and optimization components. In particular, we investigate the complexity of the /i connection subgraph problem/, which occurs, e.g., in resource environment economics and social networks. We present results on its worst-case hardness and approximability. We then provide a typical-case analysis by means of a detailed computational study. First, we identify an easy-hard-easy pattern, coinciding with the feasibility phase transition of the problem. Second, our experimental results reveal an interesting interplay between feasibility and optimization. They surprisingly show that proving optimality of the solution of the feasible instances can be substantially easier than proving in feasibility of the infeasible instances in a computationally hard region of the problem space. We also observe an intriguing easy-hard-easy profile for the optimization component itself.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Conrad, J., Gomes, C. P., van Hoeve, W.-J., Sabharwal, A., & Suter, J. (2007). Connections in networks: hardness of feasibility versus optimality. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 16-28). Springer-verlag. https://hdl.handle.net/2078.5/228756