Goal programming using multiple objective hybrid metaheuristic algorithm

In this paper, a Goal Programming (GP) model is converted into a multi-objective optimization problem (MOO) of minimizing deviations from fixed goals. To solve the resulting MOO problem, a hybrid metaheuristic with two steps is proposed to find the Pareto set's solutions. First, a Record-to-Record Travel with an adaptive memory is used to find first non-dominated Pareto frontier solutions preemptively. Second, a Variable Neighbour Search technique with three transformation types is used to intensify every non dominated solution found in the first Pareto frontier to produce the final Pareto frontier solutions. The efficiency of the proposed approach is demonstrated by solving two nonlinear GP test problems and three engineering design problems. In all problems, multiple solutions to the GP problem are found in one single simulation run. The results prove that the proposed algorithm is robust, fast and simply structured, and manages to find high-quality solutions in short computational times by efficiently alternating search diversification and intensification using very few user-defined parameters.     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

On computing objective function values in multiple objective quadratic-linear programming

In this paper, we will consider the computation of objective function values when a nondominated frontier is searched in multiple objective quadratic-linear programming (MOQLP). Reference directions and weighted-sums constitute a methodological basis for the search. This idea leads to a parametric linear complementarity model formulation. A critical task of making a search procedure efficient, is to compute the changes in quadratic and linear objective functions efficiently when a search direction is changed or a basis change is performed. Those changes in objective functions can be computed by a so-called direct or indirect method. The direct method is a straightforward one and based on the use of unit changes in basic decision variables. Instead, the indirect method utilizes some other basic variables of the model. We will introduce the indirect method and make theoretical and empirical comparisons between the methods. Based on the comparisons, we point out that the indirect method is clearly much more efficient than the direct one.     

Using objective values to start multiple objective linear programming algorithms

We introduce in this paper a new starting mechanism for multiple-objective linear programming (MOLP) algorithms. This makes it possible to start an algorithm from any solution in objective space. The original problem is first augmented in such a way that a given starting solution is feasible. The augmentation is explicitly or implicitly controlled by one parameter during the search process, which verifies the feasibility (efficiency) of the final solution. This starting mechanism can be applied either to traditional algorithms, which search the exterior of the constraint polytope, or to algorithms moving through the interior of the constraints. We provide recommendations on the suitability of an algorithm for the various locations of a starting point in objective space. Numerical considerations illustrate these ideas.     

Analysis of the objective space in multiple objective linear programming

A multiple objective linear program is defined by a matrix C consisting of the coefficients of the linear objectives and a convex polytope X defined by the linear constraints. An analysis of the objective space Y = C[X] for this problem is presented. A characterization between a face of Y and the corresponding faces of X is obtained. This result gives a necessary and sufficient condition for a face to be efficient. The theory and examples demonstrate the collapsing (simplification) that occurs in mapping X to Y. These results form a basis for a new approach to analyzing multiple objective linear programs.     

Optimality for nonsmooth fractional multiple objective programming

In this study the necessary and sufficient optimality conditions for nonsmooth fractional multiple objective optimization problems are provided. Our idea is based on using the properties of limiting subdifferential vectors in nonsmooth analysis and a separation theorem in convex analysis.     

On duality in multiple objective linear programming

In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

Assigning students to course sections using tabu search

In this paper we describe a new student registration system which has been developed at the University of Valencia, Spain. The system has two steps. First, the students make a computer-aided course selection from the courses available at the University. Thereafter, an assignment procedure allocates students to sections in order to respect two criteria: to provide the students with satisfactory schedules and to get balanced section enrollments. The assignment process has two phases. In Phase I, we obtain a set of the best solutions for each student. The algorithm is based on the construction of maximum cardinality independent sets. In Phase II, these solution sets are put together and a tabu search algorithm looks for a satisfactory balance between course sections without causing the solution obtained for each student to worsen significantly. The system was used at the beginning of the academic year 1996/97 in the Faculty of Mathematics and could be extended in the near future to the rest of the University. This revised version was published online in June 2006 with corrections to the Cover Date.     

A converse duality theorem in multiple objective programming

Recently the author has given a duality theorem in multiple objective programming relating properly efficient solutions of the primal and dual problems. In this note the converse of that theorem is given showing that, under certain assumptions, a properly efficient solution of the dual is also a properly efficient solution of the primal.     

On multiple objective programming problems with set functions

The convexity of a subset of a σ-algebra and the convexity of a set function on a convex subset are defined. Related properties are also examined. A Farkas-Minkowski theorem for set functions is then proved. These results are used to characterize properly efficient solutions for multiple objective programming problems with set functions by associated scalar problems.     

Steepest ascent algorithms for nonconical multiple objective programming

A steepest ascent family of algorithms suitable for the direct solution of continuous variable unconstrained nonconical multiple objective programming problems is introduced. Nonconical multiple objective problems, unlike standard (conical) vector optimization problems, cannot be easily solved by examining related single objective problems. The concept of a direction of steepest ascent is generalized to the multiple objective context and the question of algorithmic convergence is treated. A computational example involving a nonconical unanimity order is given.     

Comparative studies in interactive multiple objective mathematical programming

In the past two decades, there has been a significant increase in the number of interactive algorithms proposed for solving multiple objective mathematical programming (MOMP) problems. Most of these procedures have neither been tested in real decision making situations, nor compared to each other. In this study, we emphasize the importance of comparative studies of interactive MOMP procedures and present a state of the art review. Our scope is limited to the comparisons of interactive procedures for solving deterministic, linear, integer or nonlinear constrained multiple objective optimization problems involving a single decision maker.     

Interactive multiple objective programming subject to flexible constraints

An interactive decision support system is introduced which aids in solving multiple objective programming problems subject to strict and flexible constraints. Integral part is an extension of a well-known fuzzy sets approach evaluating possible solutions by their degrees of membership to objectives and constraints. This approach is linked to classical multiple objective programming models. If the decision maker cannot determine membership functions a priori the system suggests functions dependent on the given information and interactive modifications are allowed.     

Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls

A heuristic approach based on a hybrid operation of reactive tabu search (RTS) and adaptive memory programming (AMP) is proposed to solve the vehicle routing problem with backhauls (VRPB). The RTS is used with an escape mechanism which manipulates different neighbourhood schemes in a sophisticated way in order to get a continuously balanced intensification and diversification during the search process. The adaptive memory strategy takes the search back to the unexplored regions of the search space by maintaining a set of elite solutions and using them strategically with the RTS. The AMP feature brings an extra robustness to the search process that resulted in early convergence when tested on most of the VRPB instances. We compare our algorithm against the best methods in the literature and report new best solutions for several benchmark problems.     

Multi-objective tabu search using a multinomial probability mass function

A tabu search approach to solve multi-objective combinatorial optimization problems is developed in this paper. This procedure selects an objective to become active for a given iteration with a multinomial probability mass function. The selection step eliminates two major problems of simple multi-objective methods, a priori weighting and scaling of objectives. Comparison of results on an NP-hard combinatorial problem with a previously published multi-objective tabu search approach and with a deterministic version of this approach shows that the multinomial approach is effective, tractable and flexible.     

Selecting survivors in genetic algorithm using tabu search strategies

Genetic algorithm (GA) is well-known for its effectiveness in global search and optimization. To balance selection pressure and population diversity is an important issue of designing GA. This paper proposes a novel hybridization of GA and tabu search (TS) to address this issue. The proposed method embeds the key elements of TS—tabu restriction and aspiration criterion—into the survival selection operator of GA. More specifically, the tabu restriction is used to prevent inbreeding for diversity maintenance, and the aspiration criterion is activated to provide moderate selection pressure under the tabu restriction. The interaction of tabu restriction and aspiration criterion enables survivor selection to balance selection pressure and population diversity. The experimental results on numerical and combinatorial optimization problems show that this hybridization can significantly improve GAs in terms of solution quality as well as convergence speed. An empirical analysis further identifies the influences of the TS strategies on the performance of this hybrid GA.     

Large-scale controlled rounding using tabu search with strategic oscillation

When publishing tabular data, the United States Bureau of the Census must sometimes round fractional data to integer values or round integer data to multiples of a prespecified base. Data integrity can be maintained by rounding tabular data subject to additivity constraints while minimizing the overall perturbation of the data. In this paper, we describe a heuristic based on tabu search with strategic oscillation for solving this NP-hard problem. A lower-bounding technique is developed in order to evaluate the quality of the solutions and provide a starting solution for the tabu search. Numerical results demonstrate the effectiveness of the procedure when applied to extremely large tables with up to 27,000 randomly generated entries. Additionally, the algorithm is shown to perform extremely well when applied to actual data obtained from the United States Bureau of the Census.