Mixed-integer linear programming has widespread application in process engineering. When confronted with data that has not yet revealed their true value, the introduction of uncertainty into the mathematical model poses an additional challenge on its solution. A particular difficulty arises when uncertainty is simultaneously present in the coefficients of the objective function and the constraints, yielding a general multi-parametric (mp)-MILP problem. To overcome the computational burden to derive a globally optimal solution, we propose novel approximate solution strategies. We present a two-stage method and its extension towards a dynamic decomposition algorithm for mp-MILP problems. Both approaches employ surrogate mp-MILP models that are derived from overestimating bilinear terms in the constraints via McCormick relaxations over an ab initio partition of the feasible set. We incorporate piecewise affine relaxation based models using a linearly scaling scheme and a logarithmically scaling scheme, respectively. The models are tuned by the number of partitions chosen. Problem sizes and computational requirements for the different alternatives are compared. Furthermore, the conservatism of the suboptimal solution of the mp-MILP problem for the proposed approaches is discussed.