IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v240y2015i2p328-337.html
   My bibliography  Save this article

Continuous quadratic programming formulations of optimization problems on graphs

Author

Listed:
  • Hager, William W.
  • Hungerford, James T.

Abstract

Four NP-hard optimization problems on graphs are studied: The vertex separator problem, the edge separator problem, the maximum clique problem, and the maximum independent set problem. We show that the vertex separator problem is equivalent to a continuous bilinear quadratic program. This continuous formulation is compared to known continuous quadratic programming formulations for the edge separator problem, the maximum clique problem, and the maximum independent set problem. All of these formulations, when expressed as maximization problems, are shown to follow from the convexity properties of the objective function along the edges of the feasible set. An algorithm is given which exploits the continuous formulation of the vertex separator problem to quickly compute approximate separators. Computational results are given.

Suggested Citation

  • Hager, William W. & Hungerford, James T., 2015. "Continuous quadratic programming formulations of optimization problems on graphs," European Journal of Operational Research, Elsevier, vol. 240(2), pages 328-337.
    • Handle: RePEc:eee:ejores:v:240:y:2015:i:2:p:328-337
    DOI: 10.1016/j.ejor.2014.05.042
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714004810
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.05.042?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. Raghavachari, 1969. "On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints," Operations Research, INFORMS, vol. 17(4), pages 680-684, August.
    2. Luana E. Gibbons & Donald W. Hearn & Panos M. Pardalos & Motakuri V. Ramana, 1997. "Continuous Characterizations of the Maximum Clique Problem," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 754-768, August.
    3. Mohamed Didi Biha & Marie-Jean Meurs, 2011. "An exact algorithm for solving the vertex separator problem," Journal of Global Optimization, Springer, vol. 49(3), pages 425-434, March.
    4. Bomze, Immanuel M., 2012. "Copositive optimization – Recent developments and applications," European Journal of Operational Research, Elsevier, vol. 216(3), pages 509-520.
    5. S. Lucidi & F. Rinaldi, 2010. "Exact Penalty Functions for Nonlinear Integer Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 145(3), pages 479-488, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. William W. Hager & James T. Hungerford & Ilya Safro, 2018. "A multilevel bilinear programming algorithm for the vertex separator problem," Computational Optimization and Applications, Springer, vol. 69(1), pages 189-223, January.
    2. Benlic, Una & Epitropakis, Michael G. & Burke, Edmund K., 2017. "A hybrid breakout local search and reinforcement learning approach to the vertex separator problem," European Journal of Operational Research, Elsevier, vol. 261(3), pages 803-818.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Stefano Lucidi & Francesco Rinaldi, 2010. "An Exact Penalty Global Optimization Approach for Mixed-Integer Programming Problems," DIS Technical Reports 2010-17, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    2. M. Santis & F. Rinaldi, 2012. "Continuous Reformulations for Zero–One Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 153(1), pages 75-84, April.
    3. Filippo Fabiani & Barbara Franci, 2023. "On Distributionally Robust Generalized Nash Games Defined over the Wasserstein Ball," Journal of Optimization Theory and Applications, Springer, vol. 199(1), pages 298-309, October.
    4. Immanuel M. Bomze & Michael Kahr & Markus Leitner, 2021. "Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 301-316, February.
    5. Ma, Cheng & Zhang, Liansheng, 2015. "On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 642-656.
    6. Marianna De Santis & Francesco Rinaldi, 2010. "Continuous reformulations for zero-one programming problems," DIS Technical Reports 2010-16, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    7. Tao Tan & Yanyan Li & Xingsi Li, 2011. "A Smoothing Method for Zero–One Constrained Extremum Problems," Journal of Optimization Theory and Applications, Springer, vol. 150(1), pages 65-77, July.
    8. Yuejian Peng & Qingsong Tang & Cheng Zhao, 2015. "On Lagrangians of r-uniform hypergraphs," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 812-825, October.
    9. Wong, Man Hong & Zhang, Shuzhong, 2014. "On distributional robust probability functions and their computations," European Journal of Operational Research, Elsevier, vol. 233(1), pages 23-33.
    10. Peiping Shen & Kaimin Wang & Ting Lu, 2020. "Outer space branch and bound algorithm for solving linear multiplicative programming problems," Journal of Global Optimization, Springer, vol. 78(3), pages 453-482, November.
    11. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    12. Orizon Pereira Ferreira & Yingchao Gao & Sándor Zoltán Németh & Petra Renáta Rigó, 2024. "Gradient projection method on the sphere, complementarity problems and copositivity," Journal of Global Optimization, Springer, vol. 90(1), pages 1-25, September.
    13. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    14. Yanming Chang & Yuejian Peng & Yuping Yao, 2016. "Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 881-892, February.
    15. O. I. Kostyukova & T. V. Tchemisova, 2022. "On strong duality in linear copositive programming," Journal of Global Optimization, Springer, vol. 83(3), pages 457-480, July.
    16. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    17. Benlic, Una & Epitropakis, Michael G. & Burke, Edmund K., 2017. "A hybrid breakout local search and reinforcement learning approach to the vertex separator problem," European Journal of Operational Research, Elsevier, vol. 261(3), pages 803-818.
    18. Dominik Garmatter & Margherita Porcelli & Francesco Rinaldi & Martin Stoll, 2023. "An improved penalty algorithm using model order reduction for MIPDECO problems with partial observations," Computational Optimization and Applications, Springer, vol. 84(1), pages 191-223, January.
    19. Md Saiful Islam & Md Sarowar Morshed & Md. Noor-E-Alam, 2022. "A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3023-3041, November.
    20. Li, Xiaobo & Natarajan, Karthik & Teo, Chung-Piaw & Zheng, Zhichao, 2014. "Distributionally robust mixed integer linear programs: Persistency models with applications," European Journal of Operational Research, Elsevier, vol. 233(3), pages 459-473.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:240:y:2015:i:2:p:328-337. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.