Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper focuses on integer linear programs where solutions are binary matrices, and the corresponding symmetry group is the set of all column permutations. Orbitopal fixing, as introduced in Kaibel et al. (Discrete Optim 8(4):595–610, 2011), is a technique designed to break symmetries in the special case of partitioning (resp. packing) formulations involving matrices with exactly (resp. at most) one 1-entry in each row. The main result of this paper is to extend orbitopal fixing to the full orbitope, defined as the convex hull of binary matrices with lexicographically nonincreasing columns. We determine all the variables whose values are fixed in the intersection of an hypercube face with the full orbitope. Sub-symmetries arising in a given subset of matrices are also considered, thus leading to define the full sub-orbitope in the case of the sub-symmetric group. We propose a linear time orbitopal fixing algorithm handling both symmetries and sub-symmetries. We introduce a dynamic variant of this algorithm where the lexicographical order follows the branching decisions occurring along the B&B search. Experimental results for the Unit Commitment Problem are presented. A comparison with state-of-the-art techniques is considered to show the effectiveness of the proposed variants of the algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Baum, S., Trotter, L.E.: Integer rounding and polyhedral decomposition for totally unimodular systems. In: Optimization and Operations Research, pp. 15–23. Springer (1978)

  2. Bendotti, P., Fouilhoux, P., Rottner, C.: The min-up/min-down unit commitment polytope. Journal of Combinatorial Optimization 36(3), 1024–1058 (2018)

    Article  MathSciNet  Google Scholar 

  3. Bendotti, P., Fouilhoux, P., Rottner, C.: On the complexity of the unit commitment problem. Ann. Oper. Res. 274, 119–130 (2019)

    Article  MathSciNet  Google Scholar 

  4. Berthold, T., Pfetsch, M.E.: Detecting orbitopal symmetries. In: Operations Research Proceedings 2008, pp. 433–438. Springer (2009)

  5. Borndörfer, R., Grötschel, M., Pfetsch, M.E.: A column-generation approach to line planning in public transport. Transp. Sci. 41(1), 123–132 (2007)

    Article  Google Scholar 

  6. Carrion, M., Arroyo, J.M.: A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem. IEEE Trans. Power Syst. 21, 1371–1378 (2006)

    Article  Google Scholar 

  7. Friedman, E.J.: Fundamental Domains for Integer Programs with Symmetries, pp. 146–153. Springer, Berlin (2007)

    MATH  Google Scholar 

  8. Gent, I., Kelsey, T., Linton, S., McDonald, I., Miguel, I., Smith, B.: Conditional symmetry breaking. Proc. 8th International Conference on Principles and Practice of Constraint Programming pp. 256–270 (2005)

  9. Gent, I.P., Kelsey, T., Linton, S.A., Pearson, J., Roney-Dougal, C.M.: Groupoids and conditional symmetry. In: Proc. 9th International Conference on Principles and Practice of Constraint Programming, pp. 823–830 (2007)

  10. Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The scip optimization suite 5.0. Tech. Rep. 17-61, ZIB, Takustr.7, 14195 Berlin (2017)

  11. Hojny, C., Pfetsch, M.E.: Polytopes associated with symmetry handling. Math. Program. 175(1–2), 197–240 (2019)

    Article  MathSciNet  Google Scholar 

  12. Kaibel, V., Loos, A.: Branched polyhedral systems. In: Proceedings of the 14th International IPCO Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag (2010)

  13. Kaibel, V., Peinhardt, M., Pfetsch, M.E.: Orbitopal fixing. Discrete Optim. 8(4), 595–610 (2011)

    Article  MathSciNet  Google Scholar 

  14. Kaibel, V., Pfetsch, M.: Packing and partitioning orbitopes. Math. Program. 114(1), 1–36 (2008)

    Article  MathSciNet  Google Scholar 

  15. Knueven, B., Ostrowski, J., Watson, J.P.: Exploiting identical generators in unit commitment. IEEE Trans. Power Syst. 33(4), 4496–4507 (2017)

    Article  Google Scholar 

  16. Liberti, L.: Reformulations in mathematical programming: automatic symmetry detection and exploitation. Math. Program. 131(1), 273–304 (2012)

    Article  MathSciNet  Google Scholar 

  17. Liberti, L., Ostrowski, J.: Stabilizer-based symmetry breaking constraints for mathematical programs. J. Glob. Optim. 60(2), 183–194 (2014)

    Article  MathSciNet  Google Scholar 

  18. Loos, A.: Describing orbitopes by linear inequalities and projection based tools. Ph.D. thesis, Universität Magdeburg (2011)

  19. Margot, F.: Pruning by isomorphism in Branch-and-Cut. In: Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 304–317. Springer-Verlag, London, UK (2001)

  20. Margot, F.: Exploiting orbits in symmetric ILP. Math. Program. 98(1), 3–21 (2003)

    Article  MathSciNet  Google Scholar 

  21. Margot, F.: Symmetry in Integer Linear Programming, pp. 647–686. Springer, Berlin (2010)

    MATH  Google Scholar 

  22. Ostrowski, J.: Symmetry in integer programming. Ph.D. thesis, Lehigh University (2008)

  23. Ostrowski, J., Anjos, M., Vannelli, A.: Modified orbital branching for structured symmetry with an application to unit commitment. Math. Program. 150(1), 99–129 (2015)

    Article  MathSciNet  Google Scholar 

  24. Ostrowski, J., Anjos, M.F., Vannelli, A.: Tight mixed integer linear programming formulations for the unit commitment problem. IEEE Trans. Power Syst. (2012). https://doi.org/10.1109/tpwrs.2011.2162008

    Article  Google Scholar 

  25. Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Constraint Orbital Branching, pp. 225–239. Springer, Berlin (2008)

    MATH  Google Scholar 

  26. Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126(1), 147–178 (2011)

    Article  MathSciNet  Google Scholar 

  27. Pan, K., Guan, Y.: A polyhedral study of the integrated minimum-up/-down time and ramping polytope. Optim. Online (2016). http://www.optimization-online.org/DB_HTML/2015/08/5070.html

  28. Pfetsch, M.E., Rehn, T.: A computational comparison of symmetry handling methods for mixed integer programs. Math. Program. Comput. 11(1), 37–93 (2019)

    Article  MathSciNet  Google Scholar 

  29. Rajan, D., Takriti, S.: Minimum up/down polytopes of the unit commitment problem with start-up costs. IBM Research Report (2005)

Download references

Author information

Authors and Affiliations

  1. Sorbonne Université, CNRS, LIP6, 75005, Paris, France

    Pascale Bendotti, Pierre Fouilhoux & Cécile Rottner

  2. EDF R&D, 7 Boulevard Gaspard Monge, 91120, Palaiseau, France

    Pascale Bendotti & Cécile Rottner

Authors
  1. Pascale Bendotti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Fouilhoux
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cécile Rottner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pierre Fouilhoux.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bendotti, P., Fouilhoux, P. & Rottner, C. Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem. Math. Program. 186, 337–372 (2021). https://doi.org/10.1007/s10107-019-01457-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-019-01457-1

Keywords

Mathematics Subject Classification

Search

Navigation