Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Fred Glover (OptTek Systems, Inc., USA) and Saïd Hanafi (Universite de Valenciennes, France)

Source Title: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends

Copyright: © 2012
|Pages: 16
DOI: 10.4018/978-1-4666-0270-0.ch001

Chapter Preview

TopWe represent the mixed integer programming problem in the form

We assume that *Ax* + *Dy* ≥ *b* includes the inequalities *U _{j}* ≥

The current paper focuses on the zero-one version of (MIP) denoted by (MIP:0-1), in which *U _{j}* = 1 for all

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*′)^{1} 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

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*.^{2}

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.^{3}

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved