Polyhedral studies on robust mixed integer programming problems

Abstract

Recently, a robust optimization approach for the optimization problems with uncertain data has been extensively studied and successfully applied to real world optimization problems. However, taking into account the uncertainty of data makes the problem more difficult than the deterministic problem. Therefore polyhedral studies on the robust optimization problems are important, since they can be applied to general robust optimization problems. In this thesis, we study valid inequalities for robust MIP problems. First, we consider the cardinality constrained robust knapsack problem with Bertsimas and Sim model. Cover inequalities are well-known valid inequalities for the ordinary knapsack solution set, and successfully used. We generalize numerous studies for ordinary cover inequalities to robust cover inequalities. A polynomial time lifting algorithm and several separation algorithms for robust cover inequalities are proposed. In addition, an exact separation algorithm for extended robust cover inequalities is presented. The computational experiments exhibit the effect of proposed algorithms. The branch-and-cut algorithms with proposed lifting and separation algorithms are tested on the robust bandwidth packing problem. Second, we consider a chance-constrained knapsack problem where weights of items are independent and normally distributed. Probabilistic cover inequalities can be defined for the chance-constrained knapsack problem. The lifting problem for probabilistic cover inequalities is NP-hard. We propose a polynomial time approximate lifting method for probabilistic cover inequalities based on the robust optimization approach. We present computational experiments on multidimensional chance-constrained knapsack problems. The results show that our lifting method reduces the computation time substantially. Third, we study the robust continuous knapsack problem with a single unbounded continuous variable. Using submodularity of the cardinality constrained robust knapsack set function, we define submodular inequalities. Proposed valid inequalities for the robust continuous knapsack problem can be applied to general robust mixed 0-1 programming problems. A polynomial time separation algorithm for the most violated submodular inequality is proposed. We prove that the convex hull of the robust continuous knapsack polyhedron can be described completely by submodular inequalities and bound inequalities. In addition, we propose a polynomial time algorithm for the robust continuous knapsack problem. The computational results on the robust knapsack problem and the robust mixed 0-1 knapsack problem show the effect of submodular inequalities.