IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v60y2014i2p183-194.html
   My bibliography  Save this article

Stabilizer-based symmetry breaking constraints for mathematical programs

Author

Listed:
  • Leo Liberti
  • James Ostrowski

Abstract

Mathematical programs whose formulation is symmetric often take a long time to solve using Branch-and-Bound type algorithms, because of the several symmetric optima. A simple technique used in these cases is to adjoin symmetry breaking constraints to the formulation before solving the problem. These constraints: (a) aim to guarantee that at least one optimum is feasible, whilst making some of the symmetric optima infeasible; and (b) are usually associated to the different orbits of the action of the formulation group on the set of variable indices. In general, one cannot adjoin symmetry breaking constraints from more than one orbit. In Liberti (Math Program A 131:273–304, doi: 10.1007/s10107-010-0351-0 , 2012 ), some (restrictive) sufficient conditions are presented which make it possible to adjoin such constraints from several orbits at the same time. In this paper we present a new, less restrictive method for the same task, and show it performs better computationally. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Leo Liberti & James Ostrowski, 2014. "Stabilizer-based symmetry breaking constraints for mathematical programs," Journal of Global Optimization, Springer, vol. 60(2), pages 183-194, October.
    • Handle: RePEc:spr:jglopt:v:60:y:2014:i:2:p:183-194
    DOI: 10.1007/s10898-013-0106-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-013-0106-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-013-0106-6?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. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    2. Matteo Fischetti & Michele Monaci & Domenico Salvagnin, 2012. "Three Ideas for the Quadratic Assignment Problem," Operations Research, INFORMS, vol. 60(4), pages 954-964, August.
    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. Jasper van Doornmalen & Christopher Hojny, 2024. "Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 868-883, May.
    2. Shaoze Li & Zhibin Deng & Cheng Lu & Junhao Wu & Jinyu Dai & Qiao Wang, 2023. "An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints," Computational Optimization and Applications, Springer, vol. 86(1), pages 241-273, September.
    3. Gustavo Dias & Leo Liberti, 2021. "Exploiting symmetries in mathematical programming via orbital independence," Annals of Operations Research, Springer, vol. 298(1), pages 149-182, March.

    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. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    2. Dollevoet, Twan & van Essen, J. Theresia & Glorie, Kristiaan M., 2018. "Solution methods for the tray optimization problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1070-1084.
    3. Ali, Agha Iqbal & O'Connor, Debra J., 2010. "The impact of distribution system characteristics on computational tractability," European Journal of Operational Research, Elsevier, vol. 200(2), pages 323-333, January.
    4. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.
    5. Martina Fischetti & Michele Monaci, 2016. "Proximity search heuristics for wind farm optimal layout," Journal of Heuristics, Springer, vol. 22(4), pages 459-474, August.
    6. Azrah Anparasan & Miguel Lejeune, 2019. "Resource deployment and donation allocation for epidemic outbreaks," Annals of Operations Research, Springer, vol. 283(1), pages 9-32, December.
    7. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    8. Claudia Archetti & Natashia Boland & Grazia Speranza, 2017. "A Matheuristic for the Multivehicle Inventory Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 377-387, August.
    9. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    10. Sherali, Hanif D. & Van Goubergen, Dirk & Van Landeghem, Hendrik, 2008. "A quantitative approach for scheduling activities to reduce set-up in multiple machine lines," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1224-1237, June.
    11. Sakine Batun & Brian T. Denton & Todd R. Huschka & Andrew J. Schaefer, 2011. "Operating Room Pooling and Parallel Surgery Processing Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 220-237, May.
    12. Hanif D. Sherali & Barbara M. P. Fraticelli & Russell D. Meller, 2003. "Enhanced Model Formulations for Optimal Facility Layout," Operations Research, INFORMS, vol. 51(4), pages 629-644, August.
    13. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 103-120, February.
    14. Ghoniem, Ahmed & Farhadi, Farbod & Reihaneh, Mohammad, 2015. "An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems," European Journal of Operational Research, Elsevier, vol. 246(1), pages 34-43.
    15. van der Gaast, J.P. & Rietveld, C.A. & Gabor, A.F. & Zhang, Y., 2011. "A Local Search Algorithm for Clustering in Software as a Service Networks," ERIM Report Series Research in Management ERS-2011-004-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    16. A Ghoniem & H D Sherali, 2011. "Set partitioning and packing versus assignment formulations for subassembly matching problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(11), pages 2023-2033, November.
    17. Feng, Chenjia & Shao, Chengcheng & Wang, Xifan, 2021. "CSP clustering in unit commitment for power system production cost modeling," Renewable Energy, Elsevier, vol. 168(C), pages 1217-1228.
    18. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    19. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    20. Alexandra M. Newman & Martin Weiss, 2013. "A Survey of Linear and Mixed-Integer Optimization Tutorials," INFORMS Transactions on Education, INFORMS, vol. 14(1), pages 26-38, September.

    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:spr:jglopt:v:60:y:2014:i:2:p:183-194. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.