Max-Min Linear Program
Jump to navigation
Jump to search
See: Linear Program, Min-Max Linear Program, Integer Linear Program.
References
2011
- (Floréen et al., 2011) ⇒ Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. (2011). “Local Approximability of Max-Min and Min-Max Linear Programs.” In: Theory of Computing Systems Journal, 49(4). doi:10.1007/s00224-010-9303-6
- QUOTE: In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a i of A has at most ΔI positive elements, and each row c k of C has at most ΔK positive elements.
1973
- (Falk, 1973) ⇒ James E. Falk. (1973). “A Linear Max — Min Problem.” In: Mathematical Programming, 5(1). doi:10.1007/BF01580119
- ABSTRACT: We consider a two person max — min problem in which the maximizing player moves first and the minimizing player has perfect information of the outcome of this move. The move of the maximizing player influences not only the objective function but also the constraints of the minimizing player. The joint constraints as well as the objective function are assumed to be linear.
For this problem it is shown that the familiar inequality min max ges max min is reversed due to the influence of the joint constraints. The problem is characterized as a nonconvex program and a method of solution based on the branch and bound philosophy is given. A small example is presented to illustrate the algorithm.
- ABSTRACT: We consider a two person max — min problem in which the maximizing player moves first and the minimizing player has perfect information of the outcome of this move. The move of the maximizing player influences not only the objective function but also the constraints of the minimizing player. The joint constraints as well as the objective function are assumed to be linear.