AEGISi: Attribute Experimentation Guiding Improvement Searches Inline Framework

AEGISi: Attribute Experimentation Guiding Improvement Searches Inline Framework

Michael Racer, Robin Lovgren
DOI: 10.4018/IJORIS.2016040102
(Individual Articles)
No Current Special Offers


The quality of a solution to an integer programming problem is a function of a number of elements. Lightly constrained problems are easier to solve than those with tighter constraints. Local search methods generally perform better than greedy methods. In the companion paper to this one, the authors investigated how peripheral information could be gathered and utilized to improve solving subsequent problems of the same type. In the current paper, they extend this to the dynamic environment – that is, utilizing such “peripheral” information as the solver is in progress, in order to determine how best to proceed.
Article Preview

1. Introduction

In our exposition, we will discuss the Generalized Assignment Problem and the Mixed Model Sequencing Problem. Through these, we will show the variety of ways in which AEGIS can be employed, as well as provide some concrete examples of how the solution process is improved as a result.

The AEGIS system is intended to be a metaheuristic environment for solving combinatorial optimization problems. The name itself indicates the three major aspects of the system:

  • Attribute Experimentation: Experimentation is key, and can be done either prior to any formal decision-making, or incidental to it. By collecting data on historical and in-process solutions, we expect to identify relationships between non-objective attributes and the objective itself.

  • Guiding: The purpose of the experimentation is to provide tools/measures that will lead the analyst in solving a problem.

  • Improvement Searches: The process is implemented within an iterative construction environment. (However, as we shall show later, the framework is intended to suggest that one using this framework also consider rational mechanisms for decomposing an incumbent solution.)

The goal of this paper is to provide a framework in which historical information is combined with intermediate solution attributes (ISA’s), and decisions are made while the problem is being solved.

The remainder of the paper is organized as follows. The second section identifies other research that has a relationship with AEGISi. Section three discusses the dynamics of AEGISi, developing the framework for the metaheuristic used in immediate conjunction with a suite of solvers. The fourth section expands on the general discussion, focusing on two of the key components in AEGISi. In the next two sections, we show how two AEGISi systems were developed. A detailed case review is done for the Mixed Model Sequencing with Due Dates (MMSDD) Problem, along with an abbreviated look at the Generalized Assignment Problem (GAP). We then conclude with a brief review of our findings, and some ideas for follow-up research.


2. Literature Review

In the companion paper to this one (Racer & Lovgren, 2009), we presented a fairly comprehensive review of literature that relates to the AEGIS framework; the entire reference list is included here as well. In this paper, our review focuses primarily on other studies that are multi-algorithmic in nature.

In general, what we propose for the in-line AEGIS is a construct of the following form: Given the current solution state of some instance of a problem, (where the state can be a function of objective, status of constraints, current solver, solver parameters, etc.) determine the next step in the solution process (e.g., change solver, change parameters, terminate).

Hybrid algorithms, (e.g. Amini & Racer, 1995; Lovgren, 1996; many others) are degenerate forms of this construct, wherein there is not a formal consideration of the state. The work by Cramer, Dennis, Frank, Lewis, & Shubin, (1994) on non-linear problems is also typical of this form. The multi-disciplinary optimization (MDO) framework of theirs suggests sequencing through different solvers, each focusing on a different objective function element. For instance, their solution methodology for wing design iterates between an algorithm for designing the wing with respect to static conditions, and then re-evaluating that design with respect to dynamic, in-flight, performance.

A second area of interest to us, for reasons that we’ll explore in the next section, is that of axiomatic design (AD). Several good references are: Cochran & Reynal (1996); Lindholm, Tate, & Harutunian, (1999); and Gu, Hashemian, & Nee, (2004). The basic structure is shown in Figure 1.

Figure 1.

Axiomatic design environment


Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 14: 1 Issue (2023)
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing