Robust Binary Linear Programming Under Implementation Uncertainty

This paper studies binary linear programming problems in the presence of uncertainties that may cause solution values to change during implementation. This type of uncertainty, termed implementation uncertainty, is modeled explicitly affecting the decision variables rather than model parameters. The binary nature of the decision variables invalidates the use of the existing models for this type of uncertainty. The robust solutions obtained are optimal for a worst-case min-max objective and allow a controlled degree of infeasibility with respect to the associated deterministic problem. Structural properties are used to reformulate the problem as a mixed-integer linear binary program. The degree of solution conservatism is controlled by combining both constraint relaxation and cardinality-constrained parameters. Solutions for optimization problems under implementation uncertainty consist of a set of robust solutions; the selection of solutions from this possibly large set is formulated as an optimization problem over the robust set. Results from an experimental study in the context of the knapsack problem suggest the methodology yields solutions that perform well in terms of objective value and feasibility. Furthermore, the selection approach can identify robust solutions that possess desirable implementation characteristics.
Comment: 31 pages, 5 figures, 6 tables