Robust binary linear programming under implementation uncertainty
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
This dissertation focuses on binary linear programming problems (BLP) affected by uncertainties preventing the implementation of the solutions exactly as prescribed. This type of uncertainty is termed implementation uncertainty and occurs due to model fidelity limitations. This dissertation presents a model of binary variables under implementation uncertainty and develops a methodology to solve BLPs under this type of uncertainty consisting in a robust formulation (RBIU). The RBIU identifies solutions that satisfy given levels of optimality and feasibility for any realizations of the uncertainty. A solution methodology of the RBIU consists of an equivalent linear programming model. Robust solutions tend to be conservative in the sense that they sacrifice optimality to achieve the given level of feasibility. This dissertation presents two methodologies to control the conservatism of the RBIU solutions. The first method consists in controlling the feasibility relaxation level and selecting the solutions bounding the value of the objective function. The second method is an extension of a well-known method in the field of robust optimization and consists in the development of a cardinality-constrained robust BLP under implementation uncertainty (CBIU) that controls the conservatism by bounding the maximum number of variables under uncertainty with different implemented and prescribed values. The proposed concepts of robustness are applied to the knapsack problem, assignment problem and shortest path problem (SPP) under implementation uncertainty to identify their solutions immune to uncertainty and to show how particular problem structures permit to identify different important theoretical and practical properties. This work examines the properties of the robust counterparts including configurations of the control parameters, complexity and the development of solutions algorithms. This dissertation includes experimental studies to show how the proposed concepts of robustness permit to solve BLPs under implementation uncertainty and identify solutions protected against this type of uncertainty. The results of the experiments illustrate the sensitivity of the deterministic solutions to implementation uncertainty, the performance of the proposed solution methods and the different levels of the conservatism of the robust solutions. A case study involving information of a distribution company illustrates the application of the SPP under implementation uncertainty to a real problem.
