Catálogo de publicaciones - libros

New conjugate directions algorithms are proposed, which are based on an orthogonalization procedure and do not perform line searches. The orthogonalization procedure prevents the conjugate vectors set from the degeneracy, eliminates high sensitivity to computation errors pertinent to methods of conjugate directions, and thus enable us to solve large-scale minimization problems without preconditioning. Numerical experiments have confirmed high efficiency of the algorithms for minimizing large-scale quadratic functions.

We investigate the robust shortest path problem using the robust linear optimization methodology as proposed by Ben-Tal and Nemirovski. We discuss two types of uncertainty, namely, box uncertainty and ellipsoidal uncertainty. In case of box uncertainty, the robust counterpart is simple. It is a shortest path problem with the original arc lengths replaced by their upper bounds. When dealing with ellipsoidal uncertainty, we obtain a conic quadratic optimization problem with binary variables. We present an example to show that a subpath of a robust shortest path is not necessarily a robust shortest path.

In the paper a problem of finding a maximum-weight spanning connected subgraph with given vertex degrees is considered. The problem is MAX SNP-hard, because it is a generalization of a well-known Traveling Salesman Problem. Approximation algorithms are constructed for deterministic and random instances. Performance bounds of these algorithms are presented.

The paper deals with a scheduling problem on the parallel processors, in which the sum of values of all the jobs is maximized. The value of job is characterized by a stepwise non-increasing function. Establishing an order of processing of datagrams which are sent by multiprocessor router is a practical example of application of this problem. It was already proved that its single processor case is NP-hard, thus the problem is also NP-hard. Therefore, two pseudo-polynomial time algorithms for the problem with common moments of job value change and a polynomial time algorithm for the case with identical processing times are constructed. It is also constructed and experimentally tested a number of heuristic algorithms which solve the general version of the problem.

We consider a new NP-hard optimization problem, the Prize Collecting Connected Subgraph Problem, which appears as a subproblem in routing of snow plows during snow fall. In this problem we have a set of edges in an undirected network, with edge costs and edge times. Moreover there is a time budget. The problem is to find a connected subset (corresponding to a snowplow tour) of minimal cost subject to the budget constraint. This problem can be modeled using flow constraints or introducing valid inequalities. We exemplify computations for the classical Sioux Falls Network

This paper presents a Less Flexibility First (LFF) based algorithm for solving container loading problems in which boxes of given sizes are to be packed into a single container. The objective is to maximize volume utilization. LFF, firstly introduced in [An effective quasi-human heuristic for solving the rectangle packing problem, European Journal of Operations Research 141 (2002) 341], is an effective deterministic heuristic applied to 2D packing problems and generated up to 99% packing densities. Its usage is now extended to the container loading problem. Objects are packed according to their flexibilities. Less flexible objects are packed to less flexible positions of the container. Pseudo-packing procedures enable improvements on volume utilization. Encouraging packing results with up to 93% volume utilization are obtained in experiments running on benchmark cases from other authors.

Nowadays, manufacturing industries — driven by fierce competition and rising customer requirements — are forced to produce a broader range of individual products of rising quality at the same (or preferably lower) cost. Meeting these demands implies an even more complex production process and thus also an appropriately increasing request to its scheduling. Aggravatingly, vagueness of scheduling parameters — such as times and conditions — are often inherent in the production process. In addition, the search for an optimal schedule normally leads to very difficult problems (NP-hard problems in the complexity theoretical sense), which cannot be solved efficiently.

With the intent to minimize these problems, the introduced heuristic method combines standard scheduling methods with fuzzy methods to get a nearly optimal schedule within an appropriate time considering vagueness adequately.

Data Envelopment Analysis (DEA) is designed to measure the efficiency of decision making units (DMUs). A scalarizing function reduces all numerical information on inputs and outputs of a DMU to a single efficiency score. A range adjusted measure normalizes input and output values through equalization factors, already known from Multicriteria Decision Making. Cooper et al (1999) introduce a range adjusted DEA model for a non-radial measure with variable returns to scale. We extend this approach by the help of a general DEA model framework. Calculation of suitable range adjusted measures is incorporated in a web-based DEA-tool. This tool allows processing of individual sets of data with a broad choice of model characteristics.

The theoretical concept of data envelopment analysis (DEA) was published by Charnes, Cooper and Rhodes in 1978. It is a powerful tool for assessing the efficiency of decision making units (DMUs) by comparing their respective inputfactors and output quantities. More precisely, the efficiency of a DMU is measured as the relation between the sum of weighted outputs and of weighted inputs, where the weights for a DMU are the solution of a linear optimization problem. But this approach suffers from a lack of objectivity due to the fact that every DMU wants an advantageous evaluation for itself, called self-appraisal in the respective literature. The purpose of this paper is to present an extension of the evaluation process in such a way that every DMU’s performance will be calculated in an objective and fair manner. For this a fuzzy oriented approach will be formulated which yields a nonlinear optimization problem. The resulting input/output weights are a compromise of all DMU’s individual interests. The so far developed theoretical concept will be applied to a company of Taiwanese semiconductor industry. Five DMUs’ efficiencies will be calculated over three years. Professional software solves the nonlinear program and the results permit meaningful economical interpretations.

Um aus Standortdaten, die in Form digitaler Karten aus geographischen Informationssystemen vorliegen, Prognosen über die vorkommenden Pflanzenarten abzuleiten, benötigt man ein Regelwerk zur Verknüpfung dieser Informationen. Solche Regelwerke fehlen bislang. In Form linguistischer Terme liegt zwar ein bewährtes, anerkanntes Informationssystem vor, das Zeigerwertsystem nach Heinz Ellenberg, um dieses Zeigerwertsystem aber nutzbar zu machen, muss es zunächst übersetzt werden. Das hier vorgestellte System stellt diese Übersetzung in Form eines Fuzzy-Expertensystems dar. Durch die Verknüpfung von Standortdaten und den Zeigerwerten nach Ellenberg über die Übersetzung der Zeigerwerte, kann so eine Verknüpfung von Standortdaten und den vorkommenden Pflanzen abgeleitet werden. Diese Verknüpfung erfolgt in Form eines Filters, der für jede untersuchte Pflanzenart die Auftrittschance auf dem Standort in Form einer Zugehörigkeitsbeschreibung bestimmt. Auf dieser Information lassen sich eine Vielzahl weiterer Ansätze aufbauen.