A generalized Linear Programming based approach to optimal divisible load scheduling

In this paper we propose a general Linear Programming (LP) based formulation and solution methodology for obtaining optimal solution to the load distribution problem in divisible load scheduling. We exploit the power of the versatile LP formulation to propose algorithms that yield exact solutions to several very general load distribution problems for which either no solutions or only heuristic solutions were available. We consider both star (single-level tree) networks and linear daisy chain networks, having processors equipped with front-ends, that form the generic models for several important network topologies. We consider arbitrary processing node availability or release times and general models for communication delays and computation time that account for constant overheads such as start up times in communication and computation. The optimality of the LP based algorithms is proved rigorously.

Second order cone programming approaches for handling missing and uncertain data

We propose a novel second order cone programming formulation for designing robust classifiers which can handle uncertainty in observations. Similar formulations are also derived for designing regression functions which are robust to uncertainties in the regression setting. The proposed formulations are independent of the underlying distribution, requiring only the existence of second order moments. These formulations are then specialized to the case of missing values in observations for both classification and regression problems. Experiments show that the proposed formulations outperform imputation.

PROMIDS: A PROtotype multi-rIng data flow system for functional programming languages

This paper presents a detailed description of the hardware design and implementation of PROMIDS: a PROtotype Multi-rIng Data flow System for functional programming languages. The hardware constraints and the design trade-offs are discussed. The design of the functional units is described in detail. Finally, we report our experience with PROMIDS.

A mathematical programming approach to optimal Markovian switching of Poisson arrival streams to queueing systems

Motivated by certain situations in manufacturing systems and communication networks, we look into the problem of maximizing the profit in a queueing system with linear reward and cost structure and having a choice of selecting the streams of Poisson arrivals according to an independent Markov chain. We view the system as a MMPP/GI/1 queue and seek to maximize the profits by optimally choosing the stationary probabilities of the modulating Markov chain. We consider two formulations of the optimization problem. The first one (which we call the PUT problem) seeks to maximize the profit per unit time whereas the second one considers the maximization of the profit per accepted customer (the PAC problem). In each of these formulations, we explore three separate problems. In the first one, the constraints come from bounding the utilization of an infinite capacity server; in the second one the constraints arise from bounding the mean queue length of the same queue; and in the third one the finite capacity of the buffer reflect as a set of constraints. In the problems bounding the utilization factor of the queue, the solutions are given by essentially linear programs, while the problems with mean queue length constraints are linear programs if the service is exponentially distributed. The problems modeling the finite capacity queue are non-convex programs for which global maxima can be found. There is a rich relationship between the solutions of the PUT and PAC problems. In particular, the PUT solutions always make the server work at a utilization factor that is no less than that of the PAC solutions.

On BCH codes over arbitrary integer rings

Bose-C-Hocquenghem (BCH) atdes with symbols from an arbitrary fhite integer ring are derived in terms of their generator polynomials. The derivation is based on the factohation of x to the power (n) - 1 over the unit ring of an appropriate extension of the fiite integer ring. lke eomtruetion is thus shown to be similar to that for BCH codes over fink flelda.

Nonlinear programming solutions for controlling the vibration pattern of stretched strings

The problem of controlling the vibration pattern of a driven string is considered. The basic question dealt with here is to find the control forces which reduce the energy of vibration of a driven string over a prescribed portion of its length while maintaining the energy outside that length above a desired value. The criterion of keeping the response outside the region of energy reduction as close to the original response as possible is introduced as an additional constraint. The slack unconstrained minimization technique (SLUMT) has been successfully applied to solve the above problem. The effect of varying the phase of the control forces (which results in a six-variable control problem) is then studied. The nonlinear programming techniques which have been effectively used to handle problems involving many variables and constraints therefore offer a powerful tool for the solution of vibration control problems.

An integer arithmetic method to compute generalized matrix inverse and solve linear equations exactly

An algorithm that uses integer arithmetic is suggested. It transforms anm ×n matrix to a diagonal form (of the structure of Smith Normal Form). Then it computes a reflexive generalized inverse of the matrix exactly and hence solves a system of linear equations error-free.

Ordered Ports – a Language Concept for High-level Distributed Programming

A new language concept for high-level distributed programming is proposed. Programs are organised as a collection of concurrently executing processes. Some of these processes, referred to as liaison processes, have a monitor-like structure and contain ports which may be invoked by other processes for the purposes of synchronisation and communication. Synchronisation is achieved by conditional activation of ports and also through port control constructs which may directly specify the execution ordering of ports. These constructs implement a path-expression-like mechanism for synchronisation and are also equipped with options to provide conditional, non-deterministic and priority ordering of ports. The usefulness and expressive power of the proposed concepts are illustrated through solutions of several representative programming problems. Some implementation issues are also considered.

On duality in linear fractional programming

In this paper, a dual of a given linear fractional program is defined and the weak, direct and converse duality theorems are proved. Both the primal and the dual are linear fractional programs. This duality theory leads to necessary and sufficient conditions for the optimality of a given feasible solution. A unmerical example is presented to illustrate the theory in this connection. The equivalence of Charnes and Cooper dual and Dinkelbach’s parametric dual of a linear fractional program is also established.

A functional style of programming with CSP-like communication mechanisms

This paper introduces CSP-like communication mechanisms into Backus’ Functional Programming (FP) systems extended by nondeterministic constructs. Several new functionals are used to describe nondeterminism and communication in programs. The functionals union and restriction are introduced into FP systems to develop a simple algebra of programs with nondeterminism. The behaviour of other functionals proposed in this paper are characterized by the properties of union and restriction. The axiomatic semantics of communication constructs are presented. Examples show that it is possible to reason about a communicating program by first transforming it into a non-communicating program by using the axioms of communication, and then reasoning about the resulting non-communicating version of the program. It is also shown that communicating programs can be developed from non-communicating programs given as specifications by using a transformational approach.

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.

Missile battery placement for air defense: A dynamic programming approach

A procedure to evaluate surface-to-air missile battery placement patterns for air defense is presented. A measure of defense effectiveness is defined as a function of kill probability of the defense missiles and the nature of the surrounding terrain features. The concept of cumulative danger index is used to select the best path for a penetrating hostile aircraft for any given pattern of placement. The aircraft is assumed to be intelligent and well-informed. The path is generated using a dynamic programming methodology. The software package so developed can be used off-line to choose the best among a number of possible battery placement patterns.

Positional Consensus of Multi-Agent Systems Using Linear Programming Based Decentralized Control with Rectilinear Decision Domain

In this paper we develop a Linear Programming (LP) based decentralized algorithm for a group of multiple autonomous agents to achieve positional consensus. Each agent is capable of exchanging information about its position and orientation with other agents within their sensing region. The method is computationally feasible and easy to implement. Analytical results are presented. The effectiveness of the approach is illustrated with simulation results.

Design of logical topologies for wavelength-routed optical networks

his paper studies the problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology, The physical topology consists of the nodes and fiber links in the network, On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics, The set of lightpaths along with the nodes constitutes the logical topology, For a given network physical topology and traffic pattern (relative traffic distribution among the source-destination pairs), our objective is to design the logical topology and the routing algorithm on that topology so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology), We will see that ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays, On the other hand, in all our examples, imposing it results in a minimal increase in congestion, While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small, We formulate the combined logical topology design and routing problem described above (ignoring the constraint on the number of available wavelengths) as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network, Since this programming problem is computationally intractable for larger networks, we split it into two subproblems: logical topology design, which is computationally hard and will probably require heuristic algorithms, and routing, which can be solved by a linear program, We then compare the performance of several heuristic topology design algorithms (that do take wavelength assignment constraints into account) against that of randomly generated topologies, as well as lower bounds derived in the paper.

Solving linear programming problems exactly

A linear programming problem in an inequality form having a bounded solution is solved error-free using an algorithm that sorts the inequalities, removes the redundant ones, and uses the p-adic arithmetic. (C) Elsevier Science Inc., 1997