(598g) On Discretization Based Global Optimization for Mixed-Integer Bilinear Programs

Mixed-integer bilinear programs (MIBLP) arise from many engineering problems [1]. A typical example is the multiperiod gasoline blending problem, where the bilinear terms are used to describe the contents of liquid flows after blending and each integer variable is used to indicate whether a blender is to receive or deliver flows in a certain time period. Due to the nonconvexity of the bilinear terms and the integer variables, solving MIBLP to global optimality is difficult, especially when the problem size is large (e.g., when the number of time periods is large).

Recently, discretization based global optimization methods have received a lot of attention for solving MIBLPs (e.g., [2][3]). The basic idea is to discretize one of the variables in each bilinear term and represent thediscretized variables withbinary variables, then reformulate the ‘discretized problem’ into a mixed-integer linear program (MILP) via exact linearization [4]. The MILP problem obtained from discretization is a restriction of the original MIBLP problem, and a slightly modified MILP is a relaxation of the original MIBLP.When the resolution of discretization is increased, the restriction MILP and the relaxation MILP both approach the original MIBLP, and eventually converge to a global optimal solution(in a finite number of iterations).

In this presentation, we first discuss alternative ways to discretization of continuous variables in MIBLPs. All existing discretization approaches employ a radix-based framework, where the integer variable that approximates the continuous variable is expressed through a numerical system with a predefined radix or base. In the process systems engineering community, the 10-based framework is often used for discretization (and the resulting method is called multiparamatric disaggregation technique [2]); while in the operations research community, the 2-based framework is often used [5]. We start our discussion with a general R-based framework, and point out the conditions under which the continuous relaxation of the ‘discretized bilinear term’ is a convex hull relaxation. This result can help people choose an appropriate base for discretization. Then we propose an enhanced R-based framework, which guarantees convex hull relaxation of the ‘discretized bilinear term’ but with the expense of additional constraints.

Second, we discuss a new iterative global optimization procedure for efficient solution of MIBLPs. The basic idea is to refine the discretization according to the solution of the previously solved MILP relaxation. For example, if the solution of a continuous variable in the MILP relaxation is at the middle of two adjacent discretization points of the variable, then the resolution of discretization is doubled in the next iteration. However, with a fixed radix, the adaptive discretization strategy may result in unnecessarily many binary variables. To overcome this difficulty, we propose a hybrid discretization framework that allows a numerical system with multiple bases, so that in each iteration a different base may be selected according to the desired resolution of discretization. We also prove that the hybrid framework guarantees convex hull relaxation of the ‘discretized bilinear term’.

We verify our theoretical analysis results via a set of MIBLP problems from the literature. The simulation results will also demonstrate the computational advantages of the proposed global optimization method over a state-of-the-art global optimization solver.

References

[1]Castro, P. M., 2016. Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems. Journal of GlobalOptimization 64 (4), 765-784.

[2]Kolodziej, S., Castro, P. M., Grossmann, I. E., 2013a. Global optimization ofbilinear programs with a multiparametric disaggregation technique. Journalof Global Optimization 57 (4), 1039-1063.

[3]Kolodziej, S. P., Grossmann, I. E., Furman, K. C., Sawaya, N. W., 2013b. Adiscretization-based approach for the optimization of the multiperiod blendscheduling problem. Computers & Chemical Engineering 53, 122-142.

[4]Bemporad,A., Morari, M, 1999. Control of systems integrating logic, dynamics, and constraints. Automatica 35, 407-427.

[5]Gupte, A., Ahmed, S., Cheon, M. S., Dey, S., 2013. Solving mixed integerbilinear problems using MILPformulations. SIAM Journal on Optimization23 (2), 721-744.