Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • local search  (7)
  • Dualität  (4)
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 16 (1994), S. 187-191 
    ISSN: 1436-6304
    Keywords: Nonlinear programming ; duality ; solution methods ; parametric programming ; multicriteria optimization ; ill-posed problems ; Nichtlineare Optimierung ; Dualität ; Lösungsverfahren ; Parametrische Optimierung ; Vektor-Optimierung ; unlösbare Aufgaben
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Bei der Untersuchung von mathematischen Optimierungsproblemen und Lösungsmethoden liefert die Dualitätstheorie ein wichtiges Hilfsmittel. Die Konzepte derRegularisierung undStabilisierung des Ausgangsproblems erlauben eine Verbesserung des Verhaltens in praktischen Lösungsverfahren. Die nachfolgenden Untersuchungen behandeln die Dualität derartiger Regularisierungen sowie die Bildung vonHüllfunktionen. Die Bearbeitung sogenannter „unlösbarer Optimierungsprobleme“ (Eremin) durch Parametrisierung verdeutlicht die praktische Bedeutung dieses Konzeptes für numerische Verfahren. Darüber hinaus zeigen die Ergebnisse Anwendungsmöglichkeiten zur Lösung von Aufgaben der Parametrischen und Vektor-Optimierung.
    Notes: Abstract For the study of mathematical programming problems and solution methods the duality theory forms a powerful tool. There are also some concepts ofregularization andstabilization of a given problem for a better behavior in practical solution procedures. The aim of this paper is the investigation of duality aspects of such regularizations and the forming ofhullfunctions on the other hand. Applications for handling of so-calledill-posed problems (Eremin) using some parametrizations of the original problem will emphasize the importance for practical numerical methods, especially. This results will inspire some applications to solution methods for parametric and multicriteria optimization.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    ISSN: 1436-6304
    Keywords: Graph partitioning ; local search ; real timevideo signal processing ; Graphen-Partitionierung ; Lokale Suche ; Real-time Videosignalverarbeitung
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Videoalgorithmen transformieren Videosignale, also die zur Bilderzeugung notwendigen Informationseinheiten, um Bildqualität oder die Möglichkeiten spezieller Features, wie Teletext oder Bild-in-Bild-Wiedergabe, zu erhöhen. Eigene, anwendungsspezifische und häufig nur einem Videoalgorithmus zuteilbare, schnelle Videosignalprozessoren sind für die Ausführung von Videoalgorithmen verantwortlich. Die Zuordnung der Algorithmen und Prozessoren ist, aufgrund der großen Zahl zu beachtender Restriktionen, ein NP-schweres Problem, so daß eine Aufspaltung in die drei Teilprobleme Terminierung, Partitionierung und Scheduling von Operationen sinnvoll wird. In der vorliegenden Arbeit werden das Partitionierungsproblem und die Beschreibung von Videoalgorithmen mittels Signalflußgraphen betrachtet. Ein auf lokaler Suche basierendes Lösungsverfahren erzeugt rekursiv Bipartitionen des Graphen, die komplexe Nachbarschaften variabler Tiefe generieren. Rechenergebnisse zeigen, daß die vielzitierte Universalität und Flexibilität lokaler Suchverfahren erfolgreich zur Lösung schwieriger, stark restringierter Probleme genutzt werden können.
    Notes: Abstract We discuss the use of local search techniques for mapping video algorithms onto programmable high-performance video signal processors. The mapping problem is very complex due to many constraints that need to be satisfied in order to obtain a feasible solution. The complexity is reduced by decomposing the mapping problem into three subproblems, namely delay management, partitioning, and scheduling. We present the partitioning problem and the representation of video algorithms by signal flow graphs. Furthermore, we propose a solution strategy that is based on recursive bipartitioning of these graphs. The bipartitions are generated using a variable-depth search algorithm. The results demonstrate that the frequently cited flexibility of local search techniques can be successfully exploited in handling complicated problems.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 3
    ISSN: 1436-6304
    Keywords: Optimization ; local search ; heuristic ; threshold accepting ; quadratic assignment problem ; Optimierung ; lokale Suchverfahren ; Heuristik ; Threshold Accepting ; Quadratisches Zuordnungsproblem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Im vorliegenden Beitrag wird eine Modifizierung der Threshold Accepting Heuristik von Dueck und Scheuer vorgeschlagen. Anstelle diskreter Schwellenwerte wird eine Schwellenwertfunktion verwendet, die vom Abkühlungsplan beim Simulated Annealing inspiriert ist. Desweiteren ist die Iterationszahl auf jeder Ebene des Verfahrens nunmehr eine Funktion des aktuellen sowie des Ausgangsschwellenwertes. Anhand dieses Vorgehensschemas untersuchen wir den Trade-off von Lösungsqualität und Konvergenzgeschwindigkeit bei verschiedenen Standardbeispielen des bekannten Quadratischen Zuordnungsproblems. Auch die Qualität und Zuverlässigkeit einer Multistart-Version kurzer TA-Läufe wird mit den Ergebnissen ausführlicher Läufe bei gleichen CPU-Zeiten verglichen, um Rückschlüsse auf die sinnvollere Optimierungsstrategie zu erhalten. In der Literatur verwenden unterschiedliche Autoren häufig sehr verschiedene Anzahlen zufälliger Startlösungen in ihren numerischen Experimenten. Wir untersuchen daher auch, wie sich eine Variation dieser Anzahl auf die TA-Ergebnisse auswirkt.
    Notes: Abstract In this paper we propose a modification of the threshold accepting heuristic by Dueck and Scheuer. Instead of using discrete threshold values a threshold function similar to the cooling schedule of simulated annealing is used. Furthermore, the number of iterations during each step of the heuristic is a function of the current and the initial threshold value. Using this scheme, we investigate the trade-off between solution quality and convergence speed on different instances of the well known quadratic assignment problem. In a second set of experiments the results of a multistart-version of TA are compared with the results of unique long runs at identical CPU-requirements to identify the better optimization strategy. Since, generally, in the literature the number of starting solutions for QAP-heuristics appears to be chosen on a rather arbitrary basis, we also highlight how varying this number influences the TA-results.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 18 (1996), S. 51-59 
    ISSN: 1436-6304
    Keywords: Lot-sizing ; scheduling ; discrete lot-sizing and scheduling ; sequence dependent setup costs ; local search ; production planning and control ; Losgrößenplanung ; Ablaufplanung ; reihenfolgeabhängige Rüstkosten ; lokale Suchverfahren ; Produktionsplanung und -steuerung
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Dieser Beitrag beschäftigt sich mit der Ablaufplanung für eine Engpaßmaschine unter besonderer Berücksichtigung reihenfolgeabhängiger Rüstkosten. Neben Rüstkosten sind von Losgrößen abhängige Lagerkosten entscheidungsrelevant. Die Losgrößen sind dabei unter Berücksichtigung der Maschinenkapazität in einem vorgegebenen Planungszeitraum so zu bestimmen, daß alle Teilebedarfe termingerecht in ausreichender Menge befriedigt werden. Zur Lösung des Planungsproblems entwickeln wir zunächst ein neues Modell. Es unterscheidet sich von dem von Fleischmann eingeführten Modell (the discrete lot-sizing problem with sequence dependent setup costs, DLSPSD) dadurch, daß es statt diskrete kontinuierliche Losgrößen zuläßt und daß der Rüstzustand bei Stillstand der Maschine erhalten bleibt. Zur Lösung des Problems wird eine prioritätsregelbasierte Heuristik vorgeschlagen. Die Prioritätswerte und dadurch auch die Lösungsgüte des Verfahrens hängen von zwei Parametern ab. Ein Suchverfahren zur Bestimmung geeigneter Parameterwerte wird vorgestellt. Anhand kleinerer optimal gelöster Datensätze wird gezeigt, daß die Lösungsgüte der Heuristik akzeptabel ist. Für größere Datensätze wird ein Vergleich mit dem von Fleischmann für das DLSPSD vorgeschlagenen Verfahren durchgeführt. Das Verfahren von Fleischmann liefert, bedingt durch die diskrete Losgrößenbildung, nur eine obere Schranke für die hier betrachtete Problemstellung. Der Vergleich zeigt, daß die prioritätsregelbasierte Heuristik dem Verfahren von Fleischmann hinsichtlich der betrachteten Problemstellung überlegen ist.
    Notes: Abstract In this paper we consider a single-stage system where a number of different items have to be manufactured on one machine. Expenditures for the setups depend on the sequence in which items are scheduled on the machine. Holding costs are incurred for holding items in inventory. The demand of the items has to be satisfied without delay, i.e. shortages are not allowed. The objective is to compute a schedule such that the sum of holding and setup costs is minimized with respect to capacity constraints. For this problem which we call capacitated lot-sizing problem with sequence dependent setup costs (CLSD) we formulate a new model. The main differences between the new model and the discrete lot-sizing problem with sequence dependent setup costs (DLSDSD), introduced by Fleischmann, is that continuous lot-sizes are allowed and the setup state can be preserved over idle time. For the solution of the new model we present a heuristic which applies a priority rule. Since the priority values are affected by two significant parameters, we perform a local search in the parameter space to obtain low cost solutions. The solution quality is analyzed by a computational study. The comparison with optimal solutions of small instances shows that the solution quality of our heuristic is acceptable. The Fleischmann approach for the DLSPSD computes upper bounds for our new problem. On the basis of larger instances we show that our heuristic is more efficient to solve the CLSD.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 16 (1994), S. 261-265 
    ISSN: 1436-6304
    Keywords: Vector optimization ; vectorial approximation ; optimality conditions ; properly efficiency ; duality ; Vektoroptimierung ; vektorielle Approximation ; Optimalitätsbedingungen ; eigentliche Effizienz ; Dualität
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In der Arbeit werden eigentlich effiziente Lösungen für ein allgemeines vektorielles Bestapproximationsproblem betrachtet. Das Approximations-problem ist auf der Basis vektorieller Normen formuliert. Unter Verwendung von Skalarisierung werden notwendige und hinreichende Optimalitätsbedingungen hergeleitet. Dazu wird insbesondere ein skalares Dualproblem konstruiert und es werden entsprechende Dualitätsaussagen angegeben. Weiterhin werden Optimalitätsbedingungen in Subdifferentialform dargestellt. Für die Notwendigkeit der Optimalitätsbedingungen sind insbesondere Konvexitätsvoraussetzungen wesentlich. Unter jedoch sehr schwachen Voraussetzungen sind diese Bedingungen hinreichend.
    Notes: Abstract In the present paper a general vectorial best approximation problem using vectorial norms with respect to properly efficient solutions is considered. Necessary and sufficient optimality conditions for such solutions are derived. This is done on base of scalarization and studying a corresponding dual problem to the scalar optimization problem. Also optimality conditions in subdifferential form are formulated. For the necessity of the optimality conditions especially convexity assumptions are essential. But under only very weak supposition these conditions are sufficient.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 19 (1997), S. 11-21 
    ISSN: 1436-6304
    Keywords: Lotsizing ; scheduling ; sequence-dependent setup costs ; local search ; threshold accepting ; Losgrößenplanung ; Reihenfolgeplanung ; reihenfolgeabhängige Rüstkosten ; lokale Suche ; Threshold Accepting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Das GLSP (GeneralLotsizing andSchedulingProblem) stellt ein neues Modell zur integrierten Losgrößen- und Reihenfolgeplanung dar. Betrachtet wird eine Maschine mit begrenzter Kapazität, für die Lose in kontinuierlicher Größe und die zugehörige Auflagereihenfolge bestimmt werden sollen. Zielkriterium sind minimale Lagerund (reihenfolgeabhängige) Rüstkosten für gegebene dynamische Bedarfe mehrerer Produkte. Die Lösungen sind unabhängig von einer vorab festgelegten Periodeneinteilung des Planungszeitraums. Das GLSP verallgemeinert daher bekannte Modelle, die eine bestimmte Zeitstruktur voraussetzen. Es werden drei unterschiedliche Local-Search-Heuristiken zur Lösung des Problems präsentiert, die auf Basis des „Threshold Accepting”-Prinzips arbeiten. Der Vergleich mit heuristischen und optimalen Lösungen für ein verwandtes Problem zeigt, daß die Ergebnisse durchaus ermutigend für Erweiterungen des Modells sind.
    Notes: Abstract The GLSP (GeneralLotsizing andSchedulingProblem) addresses the problem of integrating lotsizing and scheduling of several products on a single, capacitated machine. Continuous lotsizes, meeting deterministic, dynamic demands, are determined and scheduled with the objective of minimizing inventory holding costs and sequence-dependent setup costs. As the schedule is independent of predefined time periods, the GLSP generalizes known models using restricted time structures. Three variants of a local search algorithm, based onthreshold accepting, are presented. Computational tests show the effectiveness of these heuristic approaches and are encouraging for further extensions of the basic model.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 7
    ISSN: 1436-6304
    Keywords: Lehrgangsplanung ; Knapsack-Problem ; Prioritätsregelverfahren ; lokale Suche ; Coursce Scheduling ; knapsack problem ; priority rule method ; local search
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Abstract Lufthansa Technical Training Ltd. (LTT) offers about 670 different types of training courses for the technical staff of Lufthansa AG and several other international airlines. The course scheduling problem faced by LTT is to develop a yearly schedule which maximizes the profit margin incurred while meeting a variety of complex precedence, temporal, and resource-related constraints. We formalize the problem as knapsack model and sketch a heuristic scheme along with a composite priority rule. We describe a local search method to determine well-suited weights for the weighted composite rule. The operational planning situation of 1996 served as our test instance. It turned out that the best schedule computed by the proposed method is substantially better in terms of the profit margin incurred than the solution manually constructed by LTT.
    Notes: Zusammenfassung Die Lufthansa Technical Training GmbH (LTT) ist verantwortlich für die Ausbildung des technischen Personals der Lufthansa AG und einiger anderer internationaler Fluggesellschaften. Hierzu bietet das Unternehmen ca. 670 verschiedene Typen von Lehrgängen in verschiedenen Schulungseinrichtungen an. Bei der Bestimmung eines deckungsbeitragsmaximalen Lehrgangsplanes sind neben komplexer Reihenfolgebeziehungen auch zeitliche und ressourcenbezogene Restriktionen zu beachten. Mathematisch wird die zugrundeliegende Problemstellung als Knapsack-Modell formalisiert. Zur Lösung skizzieren wir ein einfaches Prioritätsregelverfahren. Die verwendete Prioritätsregel stellt eine Kombination verschiedener gewichteter Prioritätswerte dar. Wir beschreiben ein lokales Suchverfahren zur Bestimmung geeigneter Gewichte. Die Ergebnisse auf der Basis der Frankfurter Schulungsreinrichtung des Jahres 1996 zeigen, daß die Erstellung eines Plans (ohne Datenerfassung bzw. -eingabe) in wenigen Minuten bis Stunden möglich ist, während die bisherige manuelle Planung mehr als einen Mannmonat erforderte. Weiterhin wird im Vergleich zur manuell ermittelten Lösung der Gesamtdeckungsbeitrag bei Verwendung der heuristischen Lösung um mehrere Hunderttausend DM gesteigert.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 8
    ISSN: 1436-6304
    Keywords: Fractional programming ; Dinkelbach-algorithm ; duality ; conjugate functions ; Quotientenoptimierung ; Dinkelbachansatz ; Dualität ; konjugierte Funktionen
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In diesem Artikel wird ein Quotientenvektoroptimierungsproblem betrachtet. Da solche Probleme im allgemeinen nicht konvex sind, wird das Ausgangsproblem mit Hilfe des Ansatzes von Dinkelbach in ein konvexes Optimierungsproblem transformiert. Zum transformierten Problem wird mit Hilfe von verallgemeinerten Fenchel-konjugierten Funktionen ein duales Problem formuliert. Entsprechende Dualitätssätze werden bewiesen und Rückschlüsse auf die Lösung der Ausgangsaufgabe gezogen.
    Notes: Abstract This paper deals with multicriteria fractional problems. Since this problems in general are not convex, the basic problem will be transformed into a convex optimization problem by using an extension of the conception of Dinkelbach to vector optimization. It will be formulated a dual problem to the transformed optimization problem, where conjugate functions are used. There will be proved strong and converse duality theorems with conclusions to basic fractional problem.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 17 (1995), S. 67-86 
    ISSN: 1436-6304
    Keywords: Heuristic algorithms ; local search ; reactive tabu search ; N-K model ; multi-knapsack problem ; Heuristics ; local search ; reactive tabu search ; N-K Modell ; Multiknapsack Problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Diese Arbeit entwickelt eine Variante der sogenannten „Reactive Tabu Search“ Methode (RTS), die auch für Optimierungsprobleme mit Nebenbedingungen geeignet ist. Das Verhalten dieser RTS Variante wird anhand einer Reihe von kombinatorischen Optimierungsproblemen mit und ohne Nebenbedingungen ausgetestet. Die Benchmark besteht aus einigen Beispielen des N-K Modells und des Multiknapsack Problems mit verschiedenen Größen und Schwierigkeitsstufen, die mit portablen Zufallszahlgeneratoren definiert werden. Ein Vergleich zwischen der Leistung der RTS Variante und der Leistung von Repeated Local Minima Search, Simulated Annealing, genetischen Algorithmen und neuronalen Netzen wird durchgeführt. Anschließend werden die Auswirkungen verschiedener Hashingschemata und eines ‚aspiration‘ Kriteriums im RTS Algorithmus untersucht.
    Notes: Abstract The purpose of this work is that of presenting a version of the Reactive Tabu Search method (RTS) that is suitable for constrained problems, and that of testing RTS on a series of constrained and unconstrained Combinatorial Optimization tasks. The benchmark suite consists of many instances of the N-K model and of the Multiknapsack problem with various sizes and difficulties, defined with portable random number generators. The performance of RTS is compared with that of Repeated Local Minima Search, Simulated Annealing, Genetic Algorithms, and Neural Networks. In addition, the effects of differenthashing schemes and of the presence of a simple “aspiration” criterion in the RTS algorithm are investigated.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 10
    ISSN: 1436-6304
    Keywords: Generalised assignment problem ; local search ; simulated annealing ; tabu search ; heuristics ; set partitioning ; branch and bound ; Verallgemeinertes Zuordnungsproblem ; lokale Suche ; simulated annealing ; tabu search ; set partitioning ; branch und bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Das verallgemeinerte Zuordnungsproblem (GAP) besteht darin, eine Menge von Aufträgen einer Menge von Agenten kostenminimal zuzuordnen. Jeder Auftrag wird genau einem Agenten zugeordnet; die Summe der Anforderungen der einem Agenten zugeordneten Aufträge ist durch die diesem zur Verfügung stehenden Ressourcen begrenzt. Die Arbeit gibt eine Übersicht über exakte und heuristische Lösungsverfahren zum GAP. Es wird einλ-Generierungs-Mechanismus beschrieben, wobei verschiedene Suchstrategien (ein Hybridverfahren aus Simulated Annealing und Tabu Search sowie reine Tabu Search-Verfahren) sowie Parameterkonstellationen untersucht werden. Die entwickelten Methoden beinhalten eine Anzahl von Eigenschaften, die sich für die Erzielung von optimalen Lösungen sowie guten Näherungen als geeignet erwiesen haben. Die Effektivität der Ansätze wird über den Vergleich hinsichtlich Lösungsqualität und Berechnungsanforderungen mit anderen speziellen Verfahren wie Branch und Bound, Simulated Annealing sowie Partitionierungs-Heuristiken bei Anwendung auf Standardprobleme aus der Literatur gezeigt.
    Notes: Abstract The generalised assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. Aλ-generation mechanism is introduced. Different search strategies and parameter settings are investigated for theλ-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computional requirement to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...