Abstract
The bicriteria problem of academic load distribution (ALD) and its integer linear programming (ILP) model are considered. Earlier it was shown that the search for a feasible solution to this problem is NP-hard and the cardinality of the complete set of alternatives is polynomial. For the ALD problem, the problem of finding a Pareto-optimal solution can be formulated as a weighted bin packing problem with color constraints and lower bounds on the load of the bins. In this problem, the number of bins is given and items have volume and color. For each bin, there is an upper bound on the number of different colors and this bound depends on the bin volume. For each item, coefficients of the efficiency of placing in any bin are set. In this paper, we study the ILP model for finding a Pareto-optimal solution. Parametric families of ALD instances are constructed and the L-coverings of these instances are studied. These instances have a small duality gap, in particular, it can be equal to one. We investigate the complexity of solving these families by the Land and Doig algorithm for some known branching rules. It is shown, that the iterations number grows exponentially with the number of bins.
Supported by the program of fundamental scientific researches of the SB RAS No. I.5.1., project No. 0314-2019-0019.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Hultberg, T.H., Cardoso, D.M.: The teacher assignment problem: a special case of the fixed charge transportation problem. Eur. J. Oper. Res. 101, 463–473 (1997). https://doi.org/10.1016/S0377-2217(96)00082-3
Sultanova, S.N., Tarkhov, S.V.: Modeli i algoritmy podderzhki prinyatiya resheniy pri raspredelenii uchebnoy nagruzki prepodavateley (Models and algorithms of decision support in the distribution of academic load of teachers). Vestnik UGATU 7(3), 107–114 (2006). (in Russian)
Zaozerskaya, L., Plankova, V., Devyaterikova, M.: Modeling and solving academic load distribution problem. In: CEUR Workshop Proceedings, Proceedings of the School-Seminar on Optimization Problems and their Applications (OPTA-SCL 2018), pp. 438–445. CEUR (2018)
Zaozerskaya, L.A., Plankova, V.A.: Researching and solving a bicriteria supply management problem with the given volumes of batches. J. Phys: Conf. Ser. 1210, 012164 (2019). https://doi.org/10.1088/1742-6596/1210/1/012164
Peeters, M., Degraeve, Z.: The co-printing problem: a packing problem with a color constraint. Oper. Res. 52(4), 623–638 (2004)
Kondakov, A., Kochetov, Y.: A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. In: Eremeev, A., Khachay, M., Kochetov, Y., Pardalos, P. (eds.) OPTA 2018. CCIS, vol. 871, pp. 309–320. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93800-4_25
Jeroslow, R.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105–109 (1974)
Kolpakov, R., Posypkin, M.: Asimptoticheskaya otsenka slozhnosti metoda vetvey i granits s vetvleniyem po drobnoy peremennoy dlya zadachi o rantse (Asymptotic estimate on the complexity of the branch-and-bound method with branching by a fractional variable for the knapsack problem). Diskret. Anal. Issled. Oper. 15(1), 58–81 (2008). (in Russia)
Saiko, L.: Issledovaniye moshchnosti \(L\)-nakrytiy nekotorykh zadach o pokrytii (Investigation of cardinality of \(L\)-coverings for some set covering problems). In: Discrete Optimization and Analysis of Complex Systems, pp. 76–97. VTs SO AN SSSR, Novosibirsk (1989). (in Russia)
Zaozerskaya, L.: Analysis of fractional covering of some supply management problems. J. Math. Model. Algorithms 5(2), 201–213 (2006). https://doi.org/10.1007/s10852-005-9016-z
Borisovsky, P.A., Eremeev, A.V.: A study on performance of the (1+1)-evolutionary algorithm. In: De Jong, K., Poli, R., Rowe, J. (eds.) Foundations of Genetic Algorithms, vol. 7, pp. 271–287. Morgan Kaufmann, Burlington (2003). An Imprint of Elsevier Science
Kolokolov, A.A.: Regular cuts by solving integer optimization problems. Upravlyaemye Sistemy, Institute Math. SB AS USSR 21, 18–25 (1981). (in Russian)
Kolokolov, A.A.: Regular partitions and cuts in integer programming. In: Korshunov, A.D. (ed.) Discrete Analysis and Operations Research. Mathematics and Its Applications, vol. 355, pp. 59–79. Springer, Dordrecht (1996). https://doi.org/10.1007/978-94-009-1606-7_6
Kolokolov, A.A., Zaozerskaya, L.A.: Finding and analysis of estimation of the number of iterations in integer programming algorithms using the regular partitioning method. Russ Math. 58(1), 35–46 (2014). https://doi.org/10.3103/S1066369X14010046
Kolokolov, A.A., Zaozerskaya, L.A.: Analysis of some cutting plane algorithms of integer programming. In: Stukach, O. (ed.) Dynamics of Systems, Mechanisms and Machines (Dynamics), Omsk, Russia, 15–17 November 2016, pp. 1–5. IEEE (2016). http://ieeexplore.ieee.org/document/7819028/
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24777-7
Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6), 875–890 (1996)
Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper. Res. 98, 353–371 (2000)
Kolokolov, A.A.: Some L-class enumeration algorithms for integer programming problems. In: Proceedings of the of 3rd IFIP WG-7.6 Working Conference on Optimization - Based Computer - Aided Modelling and Design, pp. 256–260. IITA, Prague, Czech Republic (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zaozerskaya, L. (2019). Analysis of Integer Programming Model of Academic Load Distribution. In: Bykadorov, I., Strusevich, V., Tchemisova, T. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Communications in Computer and Information Science, vol 1090. Springer, Cham. https://doi.org/10.1007/978-3-030-33394-2_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-33394-2_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-33393-5
Online ISBN: 978-3-030-33394-2
eBook Packages: Computer ScienceComputer Science (R0)