Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Branch and Bound

Sortuj według:

Ogranicz wyniki do:

Combinatorial approaches to the capital-budgeting problem

Pichugina O.

ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes

2016

Vol. 5, No 4

29--36

Optimization approaches, combinatorial and continuous, to a capital-budgeting problem (CBP) are presented. This NP-hard problem, traditionally modelled as a linear binary problem, is represented as a biquadratic over an intersection of a sphere and a supersphere. This allows applying nonlinear optimization to it. Also, the method of combinatorial and surface cuttings (MCSC) is adopted to (CBP). For the single constrained version (1CBP), new combinatorial models are introduced based on joint analysis of the constraint, objective function, and feasible region. Equivalence of (1CBP) to the multichoice knapsack problem (MCKP) is shown. Peculiarities of Branch&Bound techniques to (1CBP) are described.

Methods of using the Quadratic Assignment Problem solution

Kudelska I.

LogForum

2012

Vol. 8, no. 3

177--189

Background: Quadratic assignment problem (QAP) is one of the most interesting of combinatorial optimization. Was presented by Koopman and Beckamanna in 1957, as a mathematical model of the location of indivisible tasks. This problem belongs to the class NP-hard issues. This forces the application to the solution already approximate methods for tasks with a small size (over 30). Even though it is much harder than other combinatorial optimization problems, it enjoys wide interest because it models the important class of decision problems. Material and methods: The discussion was an artificial intelligence tool that allowed to solve the problem QAP, among others are: genetic algorithms, Tabu Search, Branch and Bound. Results and conclusions: QAP did not arise directly as a model for certain actions, but he found its application in many areas. Examples of applications of the problem is: arrangement of buildings on the campus of the university, layout design of electronic components in systems with large scale integration (VLSI), design a hospital, arrangement of keys on the keyboard.

Wstęp: Kwadratowy Problem Przydziału (QAP) jest jednym z najciekawszych zagadnień optymalizacji kombinatorycznej. Został przedstawiony przez Koopmana i Beckamanna w roku 1957, jako matematyczny model lokalizacji niepodzielnych zadań. Problem ten należy do klasy zagadnień NP.-trudnych. Wymusza to stosowanie do jego rozwiązania metod przybliżonych już dla zadań o niewielkim rozmiarze (powyżej 30). Mimo że jest ono znacznie trudniejsze niż inne zagadnienia optymalizacji kombinatorycznej, to cieszy się powszechnym zainteresowaniem, ponieważ modeluje ważną klasę problemów decyzyjnych. Metody: Dyskusji poddano narzędzia sztucznej inteligencji, które pozwoliły rozwiązać problem QAP, między innymi są to: algorytmy genetyczne, Tabu Search, Branch and Bound Wyniki i wnioski: Sam problem bezpośrednio nie powstał jako model pewnych działań, jednak znalazł on swoje zastosowanie w wielu dziedzinach. Przykładowymi zastosowaniami problemu jest: rozmieszczenie budynków na kampusie uczelnianym, projektowanie rozmieszczenia elementów elektronicznych w układach o wielkiej skali integracji (VLSI), projekt szpitala, rozmieszczenie klawiszy na klawiaturze.