Robust binary linear programming under implementation uncertainty

This article studies binary linear programming problems in the presence of uncertainties that may prevent implementing the computed solution. This type of uncertainty, called implementation uncertainty, is modelled affecting the decision variables rather than model parameters. The binary nature of the decision variables invalidates using existing robust models for implementation uncertainty. The robust solutions obtained are optimal for a worst-case min-max objective. Structural properties allow the reformulation of the problem as a binary linear program. Constraint relaxation and cardinality-constrained parameters control the degree of solution conservatism. An optimization problem permits the selection of solutions from the obtained set of robust solutions. Results from a case 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 with desirable implementation characteristics.

Automated summary

This article investigates binary linear programming problems in the presence of uncertainties that may hinder the implementation of the computed solution. The study introduces the concept of implementation uncertainty, which affects the decision variables rather than the model parameters. The article proposes a reformulation of the problem as a binary linear program and employs constraint relaxation and cardinality-constrained parameters to control the conservatism of the solutions. A selection approach is used to identify robust solutions with desirable implementation characteristics.