Global Optimization for Mixed 0-1 Programs with Convex or Separable Continuous Functions

Abstract

This paper proposes a global approach for solving mixed 0-1 programming problems containing convex or separable continuous functions. Given a mixed 0-1 polynomial term z = x₁x₂, ... x_ng(Y) where x₁, x₂,..., x_n are 0-1 integer variables and g(Y) is a convex or a separable continuous function, we can transform z into a set of inequalities where x₁, x₂,..., x_n and g(Y) are separated from each other. Based on this transformation, the original mixed 0-1 program can then be solved by a branch-and-bound method to obtain a global optimum.

Keywords:

• branch-and-bound
• mixed 0-1 programs
• separable programs