  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.
