Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization – Part II: Exploiting Reaction and Resistance

1. Introduction

We represent the zero-one mixed integer programming problem in the form

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

Recent adaptive memory and evolutionary metaheuristics for mixed integer programming have included proposals for introducing inequalities and target objectives to guide the search. These guidance approaches are useful in intensification and diversification strategies related to fixing subsets of variables at particular values, and in strategies that use linear programming to generate trial solutions whose variables are induced to receive integer values.

In this paper 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. Those targeting procedures solve a linear programming problem LP(x′, c′) where the objective vector c′ depends on the target solution x′. LP(x′, c′) includes the constraints of LP (and additional bounding constraints) while replacing the objective function z_o by a linear function v_o = c′x. Given a target solution x′, the objective 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 z_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 + z_o, where M is a large positive number.

A useful alternative to working with ω_o in the form specified is to solve LP(x′, c′) in two stages. The first stage minimizes v_o = c′x to yield an optimal solution x = x″, and the second stage enforces v_o = c′x″ to solve the residual problem of minimizing z_o = fx + gy. An effective way to enforce v_o = c′x″ is to fix all non-basic variables having non-zero reduced costs to compel these variables to receive their optimal first stage values throughout the second stage. This can be implemented by masking the columns for these variables in the optimal first stage basis, and then to continue the second stage from this starting basis while ignoring the masked variables and their columns. The resulting residual problem for the second stage can be significantly smaller than the first stage problem, allowing the problem for the second stage to be solved efficiently.