Mixed integer programming for the 0–1 maximum probability model

Mixed integer programming for the 0–1 maximum probability model

0.00 Avg rating0 Votes
Article ID: iaor20052317
Country: Netherlands
Volume: 156
Issue: 1
Start Page Number: 83
End Page Number: 91
Publication Date: Jul 2004
Journal: European Journal of Operational Research
Authors:
Keywords: programming: integer, programming: probabilistic
Abstract:

In this paper we study the 0–1 maximum probability model that consists in maximizing the probability that a certain quantity cTx is greater than a prescribed constant t, where c and x are n vectors. c1,…,cn are mutually independent and normally distributed random variables and x is a vector of n binary variables such that Ax⩽b, where b is an m vector and A is an m×n matrix. It is known that this problem can be formulated as a nonlinear fractional program. We show how to solve it exactly using mixed integer programming. The advantage of the approach is that it requires only standard, commercially available software. The computational results which we present show that this technique makes it possible to treat instances with up to 100 random variables in a few seconds of CPU time.

Reviews

Required fields are marked *. Your email address will not be published.