טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentVainer Aleksander
SubjectAdaptivity in Combinatorial Optimization Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Asaf Levin
Full Thesis textFull thesis text - English Version


Abstract

We consider stochastic variants of a wide class of NP-hard packing integer problems. Every problem has items, each of which is associated with stochastic information. The distribution of this stochastic information is known to the optimizer a-priori. In the optimization phase, the solution is constructed sequentially, and the act of choosing an item instantiates its stochastic information. The goal is to compute a policy that maximizes the expected value of the given objective function of the resulting solution such that the packing constraints are satisfied, where the output solution is the last feasible solution in the series of solutions which the optimizer creates during the optimization phase.

We consider both nonadaptive policies (that designate a priori a fixed permutation or a subset of variables in the solution) and adaptive policies (that can make dynamic decisions based on the history of the instantiated values of the stochastic information). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy.

For some problems we show the constant upper bound on the adaptivity gap, and for others, that this quantity is unbounded.