Accession Number ADA564073
Title Stochastic Pseudo-Boolean Optimization.
Publication Date Jul 2011
Media Count 123p
Personal Author O. Prokopyev
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.
Keywords Combinatorial optimization
Computation science
Integer optimization
Mathematical programming
Nonlinear optimization
Pseudo-boolean optimization
Stochastic optimization
Stochastic processes

Source Agency Non Paid ADAS
NTIS Subject Category 72F - Statistical Analysis
72E - Operations Research
Corporate Author Pittsburgh Univ., PA.
Document Type Technical report
Title Note Final rept. 1 May 2008-31 Jul 2011.
NTIS Issue Number 1302
Contract Number FA9550-08-1-0268

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader