Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization Part I: Exploiting Proximity

1. Notation And Problem Formulation

We represent the mixed integer programming problem in the form

We assume that Ax + Dy ≥ b includes the inequalities U_j ≥ x_j ≥ 0, j ∈ N = {1, …, N}, where some components of U_j may be infinite. The linear programming relaxation of (MIP) that results by dropping the integer requirement on x is denoted by (LP). We further assume Ax + Dy ≥ b includes an objective function constraint x_o ≤ U_o, where the bound U_o is manipulated as part of a search strategy for solving (MIP), subject to maintaining U_o < x_o*, where x_o* is the x_o value for the currently best known solution x* to (MIP).

The current paper focuses on the zero-one version of (MIP) denoted by (MIP:0-1), in which U_j = 1 for all j ∈ N. We refer to the LP relaxation of (MIP:0-1) likewise as (LP), since the identity of (LP) will be clear from the context,

In the following we make reference to two types of search strategies: those that fix subsets of variables to particular values within approaches for exploiting strongly determined and consistent variables, and those that make use of solution targeting procedures. As developed here, the latter solve a linear programming problem LP(x′,c′)¹ that includes the constraints of (LP) (and additional bounding constraints in the general (MIP) case) while replacing the objective function x_o by a linear function v_o = c′x. The vector x′ is called a target solution, and the vector c′ consists of integer coefficients c_j′ that seek to induce assignments x_j = x_j′ for different variables with varying degrees of emphasis.

We adopt the convention that each instance of LP(x′, c′) implicitly includes the (LP) objective of minimizing the function x_o = fx + gy as a secondary objective, dominated by the objective of minimizing v_o = c′x, so that the true objective function consists of minimizing ω_o = Mv_o + x_o, where M is a large positive number. As an alternative to working with ω_o in the form specified, it can be advantageous to solve LP(x′,c′) in two stages. The first stage minimizes v_o = c′x to yield an optimal solution x = x″ (with objective function value v_o″ = c′x″), and the second stage enforces v_o = v_o″ to solve the residual problem of minimizing x_o = fx + gy.²

A second convention involves an interpretation of the problem constraints. Selected instances of inequalities generated by approaches of the following sections will be understood to be included among the constraints Ax + Dy ≥ b of (LP). In our definition of LP(x′, c′) and other linear programs related to (LP), we take the liberty of representing the currently updated form of the constraints Ax + Dy ≥ b by the compact representation x ∈ X = {x: (x,y) ∈ Z}, recognizing that this involves a slight distortion in view of the fact that we implicitly minimize a function of y as well as x in these linear programs.³