Search

This paper introduces the minimum-time arbitrarily constrained distributed scheduling problem. The optimal distributed nonsequential backtracking algorithm is used by agents to schedule tasks where the tasks are related by constraints and where the assignment of tasks to agents may change during scheduling. The problem is distributed in that no agent has full knowledge either of the communication network or of the scheduling constraints. Each agent knows the assignments of the agents with which it can communicate and the scheduled times of the tasks assigned to those agents. The minimum-time arbitrarily constrained distributed scheduling problem is for the agents to use this local knowledge to find a schedule that satisfies all constraints and minimizes the time needed to complete all tasks. The optimal distributed nonsequential backtracking algorithm is able to find minimum-time schedules that satisfy all constraints. This algorithm is designed to work concurrently with a distributed assignment algorithm that satisfies certain communication requirements detailed in this paper. This paper presents proof of the algorithm’s correctness, completeness, and optimality. [ABSTRACT FROM PUBLISHER]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

One approach to coping with the apparent difficulty of many schedule-optimization problems, such as occur in machine shops and computer processing, is to devise efficient algorithms that find schedules guaranteed to be "near-optimal." This paper presents an introduction to this approach by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. The paper concludes with a brief survey of what has been accomplished to date in the area of scheduling using this approach. [ABSTRACT FROM AUTHOR]

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

This paper presents a general mathematical optimization model and the related deterministic algorithm for synthesizing heat-exchanger networks (HEN). The methodologies commonly used to solve a HEN problem are based on heuristic methods. These algorithms reach a presumed best solution with respect to the investigated set of process streams, whereas our approach determines the optimal configuration. In this paper the proposed method is applied to the solution of a few simple HEN synthesis problems and the results are compared with those obtained utilizing heuristic or meta-heuristic methods. HEN''s problem is represented by a general mathematical model that can be applied to small and medium sized problems and is solved by using a deterministic method with a reasonably brief computation time. Notably, this approach can represent a unique general model of a wide class of heat-exchanger networks, independently of their specific physical configuration. [Copyright &y& Elsevier]

This paper considers a multi-contract bidding situation in which the contracts are interrelated because of limited productive facilities and because of budgetary constraints. A dynamic programming model and computational algorithm are presented which derive a bidding strategy which maximizes total expected return from all contracts subject to the constraints. The computational algorithm is efficient in terms of storage capacity required and computation time. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

A new concept is proposed for linking algebraic modeling languages with structure-exploiting solvers. SPI (Structure-Passing Interface) is a program that retrieves structure from an anonymous mathematical program built by an algebraic modeling language. SPI passes the special structure of the problem to an SES (Structure-Exploiting Solver). An integration of SPI and SES leads to SET (Structure-Exploiting Tool) and can be used with any algebraic modeling language. This approach relies on the idea that most exploitable block structures can be easily detected from the algebraic formulation of models. It should enable algebraic modeling languages to access the large body of algorithmic techniques which require problem structure. [ABSTRACT FROM AUTHOR]

A Lagrangian column-generation procedure is developed which retains the original problem functions for column generation but uses transformed penalty functions in the Lagrangian optimization. The class of penalty functions considered maintains the original order of differentiability and often enhances the optimization operation. Convergence is proven for convex problems and limited computational experience cited where the new procedure converges two to four times faster than the standard method. Certain modifications of these techniques to attack nonconvex problems are also presented. [ABSTRACT FROM AUTHOR]

The article discusses the derivation of the analytical solution of color2gray algorithm and its application to fast color removal based on color quantization. It states that the lightness components of pixels must be used as gray-levels for the monochrome image representation in order to convert an image into a monochrome one. The effectiveness of the proposed algorithm can be achieved when its mathematical property must be carefully analyzed in various experiments.

Recently, we introduced the sorted Gaussian mixture models (SGMMs) algorithm providing the means to tradeoff performance for operational speed and thus permitting the speed-up of GMM-based classification schemes. The performance of the SGMM algorithm depends on the proper choice of the sorting function, and the proper adjustment of its parameters. In the present work, we employ particle swarm optimization (PSO) and an appropriate fitness function to find the most advantageous parameters of the sorting function. We evaluate the practical significance of our approach on the text-independent speaker verification task utilizing the NIST 2002 speaker recognition evaluation (SRE) database while following the NIST SRE experimental protocol. The experimental results demonstrate a superior performance of the SGMM algorithm using PSO when compared to the original SGMM. For comprehensiveness we also compared these results with those from a baseline Gaussian mixture model-universal background model (GMM-UBM) system. The experimental results suggest that the performance loss due to speed-up is partially mitigated using PSO-derived weights in a sorted GMM-based scheme. [ABSTRACT FROM AUTHOR]

In this report, twenty-nine integer linear programming problems, ranging from very simple to apparently rather difficult, are introduced. The results of running these problems on four different computer codes, involving five distinct algorithms, are presented as both time and iteration data. A brief description of the codes used is also included. [ABSTRACT FROM AUTHOR]