Robust Binary Linear Programming Under Implementation Uncertainty
Date
2018-05-03Metadata
Show full item recordAbstract
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.
Subject
Robust optimizationbinary linear programming
implementation uncertainty
knapsack problem
assignment problem
shortest path problem
optimization under uncertainty
Citation
Ramirez Calderon, Jose Ernesto (2018). Robust Binary Linear Programming Under Implementation Uncertainty. Doctoral dissertation, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /173513.