Current state of the art of algorithms and computer software for geometric programming

This paper attempts to consolidate over 15 years of attempts at designing algorithms for geometric programming (GP) and its extensions. The pitfalls encountered when solving GP problems and some proposed remedies are discussed in detail. A comprehensive summary of published software for the solution of GP problems is included. Also included is a numerical comparison of some of the more promising recently developed computer codes for geometric programming on a specially chosen set of GP test problems. The relative performance of these codes is measured in terms of their robustness as well as speed of computation. The performance of some general nonlinear programming (NLP) codes on the same set of test problems is also given and compared with the results for the GP codes. The paper concludes with some suggestions for future research.An earlier version of this paper was presented at the ORSA/TIMS Conference, Chicago, 1975.This work was supported in part by the National Research Council of Canada, Grant No. A-3552, Canada Council Grant No. S74-0418, and a research grant from the School of Organization and Management, Yale University. The author wishes to thank D. Himmelblau, T. Jefferson, M. Rijckaert, X. M. Martens, A. Templeman, J. J. Dinkel, G. Kochenberger, M. Ratner, L. Lasdon, and A. Jain for their cooperation in making the comparative study possible.     

Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

Optimization in Multiple-objective Linear Programming Problems with Pre-emptive Priorities

A decision-maker, using mathematical programming optimization models, is often faced with a choice of many alternative solutions optimizing the objective function. The decision may be based on secondary, tertiary or higher-order objectives. Such problems are usually handled using goal programming (GP) with pre-emptive priorities. Pre-emptive prioritization is discussed in the literature in the context of GP. This paper suggests that the two are separable, and presents algorithms to accomplish this. It argues that in a truly pre-emptive situation, direct lexicographical optimization of the objectives, without introduction of goals, has a number of advantages. In addition, when applied to special structure models such as transportation or assignment, this approach enables one to maintain the structure and hence the efficiency of those algorithms.     

Interior-point methods for nonconvex nonlinear programming: Jamming and numerical testing

The paper considers an example of Wächter and Biegler which is shown to converge to a nonstationary point for the standard primal–dual interior-point method for nonlinear programming. The reason for this failure is analyzed and a heuristic resolution is discussed. The paper then characterizes the performance of LOQO, a line-search interior-point code, on a large test set of nonlinear programming problems. Specific types of problems which can cause LOQO to fail are identified.Research of the first and third authors supported by NSF grant DMS-9870317, ONR grant N00014-98-1-0036.Research of the second author supported by NSF grant DMS-9805495.     

Goal programming using multiple objective tabu search

Goal programming (GP) is one of the most commonly used mathematical programming tools to model multiple objective optimisation (MOO) problems. There are numerous MOO problems of various complexity modelled using GP in the literature. One of the main difficulties in the GP is to solve their mathematical formulations optimally. Due to difficulties imposed by the classical solution techniques there is a trend in the literature to solve mathematical programming formulations including goal programmes, using the modern heuristics optimisation techniques, namely genetic algorithms (GA), tabu search (TS) and simulated annealing (SA). This paper uses the multiple objective tabu search (MOTS) algorithm, which was proposed previously by the author to solve GP models. In the proposed approach, GP models are first converted to their classical MOO equivalent by using some simple conversion procedures. Then the problem is solved using the MOTS algorithm. The results obtained from the computational experiment show that MOTS can be considered as a promising candidate tool for solving GP models.     

A Novel Mixed Integer Linear Programming Model for Clustering Relational Networks

Integer programming models for clustering have applications in diverse fields addressing many problems such as market segmentation and location of facilities. Integer programming models are flexible in expressing objectives subject to some special constraints of the clustering problem. They are also important for guiding clustering algorithms that are capable of handling high-dimensional data. Here, we present a novel mixed integer linear programming model especially for clustering relational networks, which have important applications in social sciences and bioinformatics. Our model is applied to several social network data sets to demonstrate its ability to detect natural network structures.     

A goal programming method for obtaining interval weights from an interval comparison matrix

Crisp comparison matrices lead to crisp weight vectors being generated. Accordingly, an interval comparison matrix should give an interval weight estimate. In this paper, a goal programming (GP) method is proposed to obtain interval weights from an interval comparison matrix, which can be either consistent or inconsistent. The interval weights are assumed to be normalized and can be derived from a GP model at a time. The proposed GP method is also applicable to crisp comparison matrices. Comparisons with an interval regression analysis method are also made. Three numerical examples including a multiple criteria decision-making (MCDM) problem with a hierarchical structure are examined to show the potential applications of the proposed GP method.     

Incorporating the Decision-maker's Preferences in the Goal-programming Model

Many algorithms have been developed for multiple-criteria decision-making problems. Goal programming (GP) is one of these algorithms. This model is a special extension of linear programming. Usually, it is not easy for the decision-maker to choose his aspiration levels a priori. Moreover, the incommensurability of the measurement units of the various objectives creates an aggregation problem. However, in the standard GP formulation, the decision-maker is not required to arbitrate among conflicting objectives. To deal with these difficulties, we explicitly introduce the structure of the decision-maker's preferences into the GP model in order to evaluate the impact of deviations from the decision-maker's aspirations levels. Easily and naturally, the idea of a generalized criterion, as introduced in the Promethee outranking method, will be used to build this structure of preferences.     

Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.     

A sequential goal programming model with fuzzy hierarchies to sustainable and responsible portfolio selection problem

Sustainable and responsible (SR) investors have to address two criteria types: both financial ones and those pertaining to sustainability and social responsibility. We present a comfortable tool for SR investors that allow them to express their preferences at two levels: first, by comparing criteria of the same nature, and second, via the comparison between the two superior level criteria (the financial and the SR objectives). Owing to the difficulty involved in determining a precise preference between the conflicting objectives, we address this by goal programming with fuzzy hierarchies (GPFH) modelling. This methodology is a modification of the lexicographic GP approach whereby the relative importance relations among the criteria are modelled by fuzzy relations. The proposed sequential handling for the SR portfolios selection provides information to the investors on the best result they can achieve in regard to their goals. An application to a set of UK-SR mutual funds is presented.     

Optimization based DC programming and DCA for hierarchical clustering

One of the most promising approaches for clustering is based on methods of mathematical programming. In this paper we propose new optimization methods based on DC (Difference of Convex functions) programming for hierarchical clustering. A bilevel hierarchical clustering model is considered with different optimization formulations. They are all nonconvex, nonsmooth optimization problems for which we investigate attractive DC optimization Algorithms called DCA. Numerical results on some artificial and real-world databases are reported. The results demonstrate that the proposed algorithms are more efficient than related existing methods.     

Solving Posynomial Geometric Programming Problems via Generalized Linear Programming

This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer.     

A heuristic file reorganization algorithm based on record clustering

The problem of file organization which we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in-place, i.e., using the file's original storage space for the newly reorganized file. The motivation for such a physical change is to improve the database system's performance. For example, by placing frequently and jointly accessed records on the same page or pages, we can try to minimize the number of page accesses made in answering a set of queeries. The optimal assignment (or reassignment) of records to clusters is exactly what record clustering algorithms attempt to do. However, record clustering algorithms usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment which they determine. Our algorithm is a companion to general record clustering algorithms since it actually transforms the file. The problem of optimal file reorganization isNP-hard. Consequently, our reorganization algorithm is based on heuristics. The algorithm's time and space requirements are reasonable and its solution is near optimal. In addition, the reorganization problem which we consider in this paper is similar to the problem of join processing when indexes are used.The research of this author was partially supported by the National Science Foundation under grant IST-8696157.     

Goal programming with linear fractional criteria

In this paper we present an extension of goal programming to include linear fractional criteria. The extension forms a natural link between goal programming (GP) and multiple objective linear fractional programming (MOLFP).     

On piecewise quadratic Newton and trust region problems

Some recent algorithms for nonsmooth optimization require solutions to certain piecewise quadratic programming subproblems. Two types of subproblems are considered in this paper. The first type seeks the minimization of a continuously differentiable and strictly convex piecewise quadratic function subject to linear equality constraints. We prove that a nonsmooth version of Newton’s method is globally and finitely convergent in this case. The second type involves the minimization of a possibly nonconvex and nondifferentiable piecewise quadratic function over a Euclidean ball. Characterizations of the global minimizer are studied under various conditions. The results extend a classical result on the trust region problem. Partially supported by National University of Singapore under grant 930033.     

An algorithm for systems welfare interactive goal programming modelling

Every human system is faced with the problem of choosing between alternative options, and methods of interactive programming have been suggested as the best way to lead decision makers reach decisions that are consistent with their preferences. However, even though a large number of interactive algorithms have been proposed for multiobjective decision making (MODM), there is yet no truly interactive goal programming (GP) algorithm, despite the preference of GP over other MODM methodologies. The current paper presents an algorithm for interactive GP modelling called SWIGP (systems welfare interactive GP) which ensures that the overall welfare of the system under consideration is adequately taken into account in the interactive process. To achieve this, this paper distinguishes between technical, allocative and economic efficiencies and combines an economic efficiency index with interactive GP process. Besides being of wide applicability, the algorithm exerts little cognitive burden on the decision maker (DM). Indeed, even if the DM is assumed to operate under conditions of complete ignorance, SWIGP provides the direction for searching the “best” compromise solution. Moreover, the algorithm converges very fast because of the economic efficiency index that complements the interactive process in aiding the DM arrive at a most preferred solution.     

On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators

This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefore, applications of Douglas—Rachford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new,generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.This paper is drawn largely from the dissertation research of the first author. The dissertation was performed at M.I.T. under the supervision of the second author, and was supported in part by the Army Research Office under grant number DAAL03-86-K-0171, and by the National Science Foundation under grant number ECS-8519058.     

Evaluation of the discrepancy of the linear congruential pseudo-random number sequencies

The discrepancy of a pseudo-random number (PRN) sequence has been defined as a quantity which measures the deviation of the sequence's distribution from the ideal uniform distribution. In this paper, we give three algorithms for computer evaluation of the discrepancy of PRN sequences. The computational results for the discrepancy of PRN sequences generated by a linear congruential method are included.This research is partially funded by Natural Sciences and Engineering Research Council of Canada, Grant No. 0GP00089. A research grant from IBM Canada through the Supercomputer Center, University of New Brunswick, is gratefully acknowledged.     

Agricultural sustainable management: a normative approach based on goal programming

This paper has two goals. It aims, first, to explore how the use of goal programming (GP) techniques within a Simonian-bounded rationality context can be an operational framework for dealing with the sustainable management of agricultural systems. Second, it goes on to apply this type of theoretical framework to a case study related to the sustainable management of irrigated agriculture in the Spanish Monegros District, where GP models are used to establish sensible compromises among economic and environmental criteria.