Minimal Representations of a Face of a Convex Polyhedron and Some Applications
Tóm tắt
In this paper, we propose a method for determining all minimal representations of a face of a polyhedron defined by a system of linear inequalities. Main difficulties for determining prime and minimal representations of a face are that the deletion of one redundant constraint can change the redundancy of other constraints and the number of descriptor index pairs for the face can be huge. To reduce computational efforts in finding all minimal representations of a face, we prove and use properties that deleting strongly redundant constraints does not change the redundancy of other constraints and all minimal representations of a face can be found only in the set of all prime representations of the face corresponding to the maximal descriptor index set for it. The proposed method is based on a top-down search strategy, is easy to implement, and has many computational advantages. Based on minimal representations of a face, a reduction of degeneracy degrees of the face and ideas to improve some known methods for finding all maximal efficient faces in multiple objective linear programming are presented. Numerical examples are given to illustrate the method.
Tài liệu tham khảo
Benson, H.P., Sayin, S.: A face search heuristic algorithm for optimizing over the efficient set. Naval Res. Log. 40, 103–116 (1993)
Boneh, A., Caron, R.J., Lemire, F.W., McDonald, J.F., Telgen, J., Vorst, A.C.F.: Note on prime representations of convex polyhedral sets. J. Optim. Theory Appl. 61, 137–142 (1989)
Ciripoi, D., Löhne, A., Weißing, B: Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver. Optimization 68, 2039–2054 (2019)
Dam, A.A.T.: Similarity Transformations between Minimal Representations of Convex Polyhedral Sets. NLR Technical Publication NLR TP 93393 (1993)
Evtushenko, Y.G., Golikov, A.I., Mollaverdy, N.: Augmented Lagrangian method for large-scale linear programming problems. Optim. Methods Softw. 20, 515–524 (2005)
Fukuda, K., Gartner, B., Szedlak, M.: Combinatorial redundancy detection. Ann. Oper. Res. 34, 315–328 (2015)
Greenberg, H.J.: Consistency, redundancy, and implied equalities in linear systems. Ann. Math. Artif. Intell. 17, 37–83 (1996)
Klintberg, E., Nilsson, M., Mardh, L.J., Gupta, A.: A primal active-set minimal-representation algorithm for polytopes with application to invariant-set calculations. In: IEEE Conference on Decision and Control. https://doi.org/10.1109/CDC.2018.8619642 (2018)
Luan, N.N., Yen, N.D.: A representation of generalized convex polyhedra and applications. Optimization 69(3), 471–492 (2020)
Marechal, A., Perin, M.: Efficient elimination of redundancies in polyhedra by raytracing. In: International Conference on Verification, Model Checking and Abstract Interpretation (2017)
Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1972)
Sayin, S.: An algorithm based on facial decomposition for finding the efficient set in multiple objective linear programming. Oper. Res. Lett. 19, 87–94 (1996)
Sayin, S.: Optimization over the efficient set using a top-down search of faces. Oper. Res. 48, 65–72 (2000)
Scholl, C., Disch, S., Pigorsch, F., Kupferschmid, S.: Computing optimized representations for non-convex polyhedra by detection and removal of redundant linear constraints. In: TACAS, LNCS, vol. 5505, pp 383–397. Springer (2009)
Sierksma, G., Tijssen, G.A.: Degeneracy degrees of constraint collections. Math. Methods Oper. Res. 53, 437–448 (2003)
Telgen, J.: Minimal representation of convex polyhedral sets. J. Optim. Theory Appl. 38, 1–24 (1982)
Tu, T.V.: Optimization over the efficient set of a parametric multiple objective linear programming problem. Eur. J. Oper. Res. 122, 570–583 (2000)
Tu, T.V.: A common formula to compute the efficient sets of a class of multiple objective linear programming problems. Optimization 64, 2065–2092 (2015)
Tu, T.V.: The maximal descriptor index set for a face of a convex polyhedral set and some applications. J. Math. Anal. Appl. 429, 395–414 (2015)
Tu, T.V.: A new method for determining all maximal efficient faces in multiple objective linear programming. Acta Math. Vietnam. 42, 1–25 (2017)
Yu, P.L., Zeleny, M.: The set of all nondominated solutions in linear cases and a multicriteria simplex method. J. Math. Anal. Appl. 49, 430–468 (1975)