×

Bounds for probabilistic integer programming problems. (English) Zbl 1173.90488

Let \(s\), \(m\), and \(n\) be positive integers, \(A\) be a real matrix of type \(m\times n\), \(T\) be an integer matrix of type \(s\times n\), \( b\) an \(m\)-dimensional real vector, \(c\) be an \(n\)-dimensional real vector, \(\xi\) be a random \(s\)-dimensional integer vector and \(p\in <0,1>\). The probabilistic integer programming seeks an \(n\)-dimensional nonnegative integer vector \(x\) such that \(\text{Prob}(Tx\geq\xi )\geq p\), \(Ax\geq b\) and \(x\) minimizes \(c^Tx\). The paper presents lower and upper bounds on the vector \(x\). The lower bound is based on the cone generation method. A simple illustrating example is given.

MSC:

90C15 Stochastic programming
90C10 Integer programming
90C27 Combinatorial optimization

Software:

AMPL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. V. P.; Vance, P. H.: Branch-and-price: column generation for solving huge integer programs. Oper. res. 46, 316-329 (1998) · Zbl 0979.90092
[2] Becker, T.; Weispfenning, V.: Gröbner bases. (1993) · Zbl 0772.13010
[3] Birge, J. R.; Louveaux, F.: Introduction to stochastic programming. (1997) · Zbl 0892.90142
[4] Charnes, A.; Cooper, W. W.; Symonds, G. H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Management sci. 4, 235-263 (1958)
[5] Chvátal, V.: Linear programming. (1983) · Zbl 0537.90067
[6] D. Dentcheva, A. Prékopa, A. Ruszczyński, Concavity and Efficient Points of Discrete Distributions in Probabilistic Programming, Math. Programming 89 (2000) 55–77. · Zbl 1033.90078
[7] Fourer, R.; Gay, D. M.; Kernighan, B. W.: AMPL: A modeling language for mathematical programming. (1993) · Zbl 0701.90062
[8] Gendreau, M.; Laporte, G.; Séguin, R.: Stochastic vehicle routing. European J. Oper. res. 88, 3-12 (1996) · Zbl 0913.90094
[9] Laporte, G.; Louveaux, F. V.; Mercure, H.: Models and exact solutions for a class of stochastic location-routing problems. European J. Oper. res. 39, 71-78 (1989) · Zbl 0676.90019
[10] Miller, L. B.; Wagner, H.: Chance-constrained programming with joint constraints. Oper. res. 13, 930-945 (1965) · Zbl 0132.40102
[11] A. Prékopa, On probabilistic constrained programming, Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, Princeton, 1970, pp. 113–138.
[12] Prékopa, A.: Contributions to the theory of stochastic programming. Math. programming 4, 202-221 (1973) · Zbl 0273.90045
[13] Prékopa, A.: Boole–bonferroni inequalities and linear programming. Oper. res. 36, 145-162 (1988) · Zbl 0642.60012
[14] Prékopa, A.: Dual method for a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Z. oper. Res. 34, 441-461 (1990) · Zbl 0724.90048
[15] Prékopa, A.: Sharp bounds on probabilities using linear programming. Oper. res. 38, 227-239 (1990) · Zbl 0727.90049
[16] Prékopa, A.: Stochastic programming. (1995) · Zbl 0834.90098
[17] Prékopa, A.; Vizvári, B.; Badics, T.: Programming under probabilistic constraint with discrete random variable. New trends in mathematical programming, 235-255 (1998) · Zbl 0907.90215
[18] Sen, S.: Relaxations for the probabilistically constrained programs with discrete random variables. Oper. res. Lett. 11, 81-86 (1992) · Zbl 0765.90071
[19] B. Vizvári, Beiträge zum Frobenius Problem, D.Sc.Nat. Dissertation, Technische Hohschule Carl Schorlemmer, Leuna-Merseburg, Germany, 1987.
[20] Tayur, S. L.; Themas, R. L.; Natraj, N. R.: An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands. Math. programming 69, 369-401 (1995) · Zbl 0839.90063
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.