Approximate solution of mp-MILP problems using piecewise affine relaxation of bilinear terms

• A two-stage method for multi-parametric mixed integer linear programming problems is proposed.
• Sub-optimal solutions are computed.
• Overestimators of bilinear terms over an ab initio partitioning of the domain are employed.
• Linear and logarithmic partitioning scheme based approximate models are studied.
• Approximate models are tunable by the number of partitions.

We propose an approximate solution strategy for multi-parametric mixed integer linear programming (mp-MILP) problems with parameter dependency at multiple locations in the model. A two-stage solution strategy, consisting of an approximation stage and a multi-parametric programming stage, is introduced. At the approximation stage, surrogate mp-MILP models are derived by overestimating bilinear terms in the constraints over an ab initio partitioning of the domain. We then incorporate piecewise affine relaxation based models using a linear partitioning scheme and a logarithmic partitioning scheme, respectively. The models are tuned by the number of partitions chosen. Problem sizes of the varied models, and computational requirements for the algorithmic procedure are compared. The conservatism of the suboptimal solution of the mp-MILP problem for the piecewise affine relaxation based two-stage method is discussed.