Solving mixed-integer robust optimization problems with interval uncertainty using Benders decomposition

Abstract

Uncertainty and integer variables often exist together in economics and engineering design problems. The goal of robust optimization problems is to find an optimal solution that has acceptable sensitivity with respect to uncertain factors. Including integer variables with or without uncertainty can lead to formulations that are computationally expensive to solve. Previous approaches for robust optimization problems under interval uncertainty involve nested optimization or are not applicable to mixed-integer problems where the objective or constraint functions are neither quadratic, nor linear. The overall objective in this paper is to present an efficient robust optimization method that does not contain nested optimization and is applicable to mixed-integer problems with quasiconvex constraints (⩽ type) and convex objective funtion. The proposed method is applied to a variety of numerical examples to test its applicability and numerical evidence is provided for convergence in general as well as some theoretical results for problems with linear constraints.

Keywords:

• robust optimization
• mixed-integer
• Benders decomposition
• interval uncertainty
• quasiconvex function

Acknowledgements

The work presented in this paper was supported in part by the Office of Naval Research Contract N000140810384. The work of the third author was also supported in part by the ONR Grant N000141310160. Such support does not constitute an endorsement by the funding agency of the opinions expressed in this paper. We would also like to thank the anonymous referees for their comments.

Notes

1 Note that Assumption 3 ensures that finding worst-case uncertainty values enables us to find a globally optimal robust solution.

2 Note that the function is not known in closed form but will be later shown to be approximated using a variation of Benders cuts.

3 Since only endpoints are considered, does not need to be distinguished from and the same procedures can be applied. However, if Δy is not integer, then taking the first integer value less than Δy will ensure an optimal robust solution.

4 Note that the complicating variables do not appear in the objective function for the master problem (14).