×

Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem. (English) Zbl 1459.90129

Summary: 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 [V. Kaibel et al., Discrete Optim. 8, No. 4, 595–610 (2011; Zbl 1235.90091)], 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.

MSC:

90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C90 Applications of mathematical programming

Citations:

Zbl 1235.90091

Software:

SCIP
PDFBibTeX XMLCite
Full Text: DOI arXiv

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) · Zbl 0404.90053
[2] Bendotti, P.; Fouilhoux, P.; Rottner, C., The min-up/min-down unit commitment polytope, Journal of Combinatorial Optimization, 36, 3, 1024-1058 (2018) · Zbl 1414.90141 · doi:10.1007/s10878-018-0273-y
[3] Bendotti, P.; Fouilhoux, P.; Rottner, C., On the complexity of the unit commitment problem, Ann. Oper. Res., 274, 119-130 (2019) · Zbl 1407.90269 · doi:10.1007/s10479-018-2827-x
[4] Berthold, T., Pfetsch, M.E.: Detecting orbitopal symmetries. In: Operations Research Proceedings 2008, pp. 433-438. Springer (2009) · Zbl 1209.90260
[5] Borndörfer, R.; Grötschel, M.; Pfetsch, ME, A column-generation approach to line planning in public transport, Transp. Sci., 41, 1, 123-132 (2007) · doi:10.1287/trsc.1060.0161
[6] Carrion, M.; Arroyo, JM, A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem, IEEE Trans. Power Syst., 21, 1371-1378 (2006) · doi:10.1109/TPWRS.2006.876672
[7] Friedman, EJ, Fundamental Domains for Integer Programs with Symmetries, 146-153 (2007), Berlin: Springer, Berlin · Zbl 1175.90296
[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) · Zbl 1153.68459
[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) · Zbl 1145.68514
[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, ME, Polytopes associated with symmetry handling, Math. Program., 175, 1-2, 197-240 (2019) · Zbl 1421.90088 · doi:10.1007/s10107-018-1239-7
[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) · Zbl 1285.90082
[13] Kaibel, V.; Peinhardt, M.; Pfetsch, ME, Orbitopal fixing, Discrete Optim., 8, 4, 595-610 (2011) · Zbl 1235.90091 · doi:10.1016/j.disopt.2011.07.001
[14] Kaibel, V.; Pfetsch, M., Packing and partitioning orbitopes, Math. Program., 114, 1, 1-36 (2008) · Zbl 1171.90004 · doi:10.1007/s10107-006-0081-5
[15] Knueven, B.; Ostrowski, J.; Watson, JP, Exploiting identical generators in unit commitment, IEEE Trans. Power Syst., 33, 4, 4496-4507 (2017) · doi:10.1109/TPWRS.2017.2783850
[16] Liberti, L., Reformulations in mathematical programming: automatic symmetry detection and exploitation, Math. Program., 131, 1, 273-304 (2012) · Zbl 1235.90103 · doi:10.1007/s10107-010-0351-0
[17] Liberti, L.; Ostrowski, J., Stabilizer-based symmetry breaking constraints for mathematical programs, J. Glob. Optim., 60, 2, 183-194 (2014) · Zbl 1312.90077 · doi:10.1007/s10898-013-0106-6
[18] Loos, A.: Describing orbitopes by linear inequalities and projection based tools. Ph.D. thesis, Universität Magdeburg (2011) · Zbl 1235.90001
[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) · Zbl 1010.90508
[20] Margot, F., Exploiting orbits in symmetric ILP, Math. Program., 98, 1, 3-21 (2003) · Zbl 1082.90070 · doi:10.1007/s10107-003-0394-6
[21] Margot, F., Symmetry in Integer Linear Programming, 647-686 (2010), Berlin: Springer, Berlin · Zbl 1187.90200
[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) · Zbl 1309.90059 · doi:10.1007/s10107-014-0812-y
[24] Ostrowski, J.; Anjos, MF; Vannelli, A., Tight mixed integer linear programming formulations for the unit commitment problem, IEEE Trans. Power Syst. (2012) · doi:10.1109/tpwrs.2011.2162008
[25] Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S., Constraint Orbital Branching, 225-239 (2008), Berlin: Springer, Berlin · Zbl 1143.90361
[26] Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S., Orbital branching, Math. Program., 126, 1, 147-178 (2011) · Zbl 1206.90101 · doi:10.1007/s10107-009-0273-x
[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, ME; Rehn, T., A computational comparison of symmetry handling methods for mixed integer programs, Math. Program. Comput., 11, 1, 37-93 (2019) · Zbl 1411.90233 · doi:10.1007/s12532-018-0140-y
[29] Rajan, D., Takriti, S.: Minimum up/down polytopes of the unit commitment problem with start-up costs. IBM Research Report (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.