|
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
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
|
