Stochastic Pseudo Boolean Optimization
Abstract Pseudo boolean (and general nonlinear integer) functions provide an extremely powerful modeling and solution tool in operations research and related areas. A large number of practical as well as purely theoretical decision problems can be easily represented and solved as optimization of a pseudo boolean or general nonlinear integer function. In the framework of this project we have considered several stochastic extensions of classical combinatorial optimization problems that involve some type of nonlinearity, typically in the objective function. We have provided respective theoretical analysis and developed advanced solution approaches. In particular, we have investigated the following topics: (i) exact solution algorithms for broad classes of two stage stochastic quadratic binary and general integer programming problems; (ii) approximation algorithms for solving a class of two stage stochastic assignment problems; (iii) theoretical analysis of two stage stochastic minimum s t cut problems; (iv) exact solution algorithm for a class of stochastic bilevel knapsack problems; (v) exact solution algorithms for a class multiple ratio fractional programming problems; and (vi) integer programming approach for solving a polyomino tiling problem with application in antenna design.