Spelling suggestions: "subject:"combinatorial aptimization"" "subject:"combinatorial foptimization""
71 
Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner / Problemas online de localização de instalações e de SteinerSan Felice, Mário César, 1985 27 August 2018 (has links)
Orientador: Orlando Lee / Tese (doutorado)  Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 20180827T12:18:11Z (GMT). No. of bitstreams: 1
SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5)
Previous issue date: 2015 / Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online SingleSource RentorBuy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rentorbuy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas / Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online SingleSource RentorBuy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rentorbuy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online PrizeCollecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have nonnegative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

72 
O problema de minimização de pilhas abertas  novas contribuições / The minization of open stacks problem  new contribuctionsClaudia Fink 19 October 2012 (has links)
O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NPDifícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltouse para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrouse eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divideo em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NPhard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain provedoptimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixedinteger programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

73 
Turán Triangles, Cell Covers, Road Placement and Train SchedulingSchultz Xavier da Silveira, Luís Fernando 29 May 2020 (has links)
In this doctoral thesis, four questions related to computational geometry are considered. The first is an extremal combinatorics question regarding triangles with vertices taken from a set of n points in convex position. More precisely, two such triangles can exhibit eight distinct configurations and, for each subset of these configurations, we are interested in the asymptotics of how many triangles one can have while avoiding configurations in the subset (as a function of n). For most of these subsets, we answer this question optimally up to a logarithmic factor in the form of several Turántype theorems. The answers for the remaining few were in turn tied to that of a longstanding open problem which appeared in the literature in the contexts of monotone matrices, tripod packing and 2comparable sets.
The second problem, called Line Segment Covering (LSC), is about covering the cells of an arrangement of line segments with these line segments, where a segment covers the cells it is incident to. Recently, a PTAS, an APX hardness proof and a FPT algorithm for variants of this problem have been shown. This paper and a
new slight generalization of one of its results is included as a chapter.
The third problem has been posed in the Sixth Annual Workshop on Geometry and Graphs and concerns the design of road networks to minimize the maximum travel time between two point sets in the plane. Traveling outside the roads costs more time per unit of distance than traveling on the roads and the total length of the roads can not exceed a budget. When the point sets are the opposing sides of a unit square and the budget is at most √2, we were able to come up with a few network designs that cover all possible cases and are provably optimal. Furthermore, when both point sets are the boundary of a unit circle, we managed to disprove the natural conjecture that a concentric circle is an optimal design.
Finally, we consider collisionavoiding schedules of unitvelocity axisaligned trains departing and arriving from points in the integer lattice. We prove a few surprising results on the existence of constant upper bounds on the maximum delay that are independent of the train network. In particular, these upper bounds are shown to always exist in two dimensions and to exist in three dimensions for unitlength trains. We also showed computationally that, for several scenarios, these upper bounds are tight.

74 
Scheduling of flow shops with synchronous movementWaldherr, Stefan 28 October 2015 (has links)
This thesis presents a thorough introduction to flow shop problems with synchronous movement which are a variant of a nonpreemptive permutation flow shop. Jobs have to be moved from one machine to the next by an unpaced synchronous transportation system, which implies that the processing is organized in synchronized cycles. This means that in each cycle the current jobs start at the same time on the corresponding machines and after processing have to wait until the last job is finished. Afterwards, all jobs are moved to the next machine simultaneously. In this thesis flow shops with synchronous movement are systematically embedded into the flow shop scheduling framework. The problem is defined for the most common objective functions as well as for many extensions and additional constraints that can be observed in real world applications. The thesis offers an extensive study of complexity of the discussed problems. Several exact and heuristic solution algorithms are proposed and evaluated. Further, a project in cooperation with a practitioner where flow shops with synchronous movement and resource constraints appear in a real world application is discussed. The results of the implemented heuristic approach are compared to the actual production of the industrial partner.

75 
Dynamic Programming MultiObjective Combinatorial OptimizationMankowski, Michal 18 October 2020 (has links)
In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multiobjective optimization algorithms: the multistage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bicriteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solution before and after every optimization stage of multistage optimization. We propose a fairly universal approach based on socalled circuits without repetitions in which each element is generated exactly one time. Such circuits represent the sets of elements under consideration (the sets of feasible solutions) and are used by counting, multistage, and bicriteria optimization algorithms. For a given optimization problem, we should describe an appropriate circuit and cost functions. Then, we can use the designed algorithms for which we already have proofs of their correctness and ways to evaluate the required number of operations and the time. We construct conventional (which work directly with elements) circuits without repetitions for matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), onedimensional clustering, optimal bitonic tour, and segmented least squares. For these problems, we evaluate the number of operations and the time required by the optimization and counting algorithms, and consider the results of computational experiments. If we cannot find a conventional circuit without repetitions for a problem, we can either create custom algorithms for optimization and counting from scratch or can transform a circuit with repetitions into a socalled syntactical circuit, which is a circuit without repetitions that works not with elements but with formulas representing these elements. We apply both approaches to the optimization of matchings in trees and apply the second approach to the 0/1 knapsack problem. We also briefly introduce our work in operation research with applications to health care. This work extends our interest in the optimization field from developing new methods included in this dissertation towards the practical application.

76 
A SeparatorBased Framework for Graph Matching ProblemsLahn, Nathaniel Adam 29 May 2020 (has links)
Given a graph, a matching is a set of vertexdisjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimumcost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, longstanding combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with nonnegative integer edge costs at most C, it is known how to compute a minimumcost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While noncombinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equalsize components by removing a relatively small portion of the graph. Several wellstudied classes of graphs have separatorlike properties, including planar graphs, minorfree graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomialfactor improvements for several openproblems in bipartite matching. / Doctor of Philosophy / Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimumcost maximumcardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.

77 
Metaraps : an effective approach for combinatorial problemsMoraga, Reinaldo J. 01 April 2002 (has links)
No description available.

78 
Algorithmic aspects of connectivity, allocation and design problemsChakrabarty, Deeparnab 23 May 2008 (has links)
Most combinatorial optimization problems are
NP hard, which imply that under well believed complexity assumptions, there exist no polynomial time
algorithms to solve them. To cope with the NPhardness, approximation algorithms which return solutions close to
the optimal, have become a rich field of study. One successful method for designing approx
imation algorithms has been to model the optimization problem as an integer program and
then using its polynomial time solvable linear programming relaxation for the design and
analysis of such algorithms. Such a technique is called the LPbased technique.
In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems
using LPbased techniques as our main tool.
Connectivity Problems:
We study the Steiner tree problem and devise new linear pro
gramming relaxations for the problem. We show an equivalence of our relaxation with the
well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class
of graphs called quasibipartite graphs, we improve the best known upper bound on the
integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation
algorithms for the Steiner tree problem on quasibipartite graphs.
Allocation Problems:
We study the budgeted al location problem of allocating a set of
indivisible items to a set of agents who bid on it but possess a hard budget constraint more
than which they are unwilling to pay. This problem is a special case of submodular welfare
maximization. We use a natural LP relaxation for the problem and improve the best known
approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox
imability factor of the problem to 15/16 and use our techniques to show inapproximability
results for many other allocation problems.
We also study online allocation problems where the set of items are unknown and appear one at a time.
Under some necessary assumptions we provide online algorithms for
many problems which attain the (almost) optimal competitive ratio. Both these works have
applications in the area of budgeted auctions, the most famous of which are the sponsored
search auctions hosted by search engines on the Internet.
Design Problems:
We formally define and study design problems which asks how the
weights of an input instance can be designed, so that the minimum (or maximum) of
a certain function of the input can be maximized (respectively, minimized). We show
if the function can be approximated to any factor $alpha$, then the optimum design can be
approximated to the same factor.
We also show that (maxmin) design problems are dual to packing problems. We use
the framework developed by our study of design problems to obtain results about fraction
ally packing Steiner trees in a "blackbox" fashion. Finally, we study integral packing of
spanning trees and provide an alternate proof of a theorem of NashWilliams and Tutte
about packing spanning trees.

79 
Inverse multiobjective combinatorial optimizationRoland, Julien 12 November 2013 (has links)
The initial question addressed in this thesis is how to take into account the multiobjective aspect of decision problems in inverse optimization. The most straightforward extension consists of finding a minimal adjustment of the objective functions coefficients such that a given feasible solution becomes efficient. However, there is not only a single question raised by inverse multiobjective optimization, because there is usually not a single efficient solution. The way we define inverse multiobjective<p>optimization takes into account this important aspect. This gives rise to many questions which are identified by a precise notation that highlights a large collection of inverse problems that could be investigated. In this thesis, a selection of inverse problems are presented and solved. This selection is motivated by their possible applications and the interesting theoretical questions they can rise in practice. / Doctorat en Sciences de l'ingénieur / info:eurepo/semantics/nonPublished

80 
REACTIVE GRASP WITH PATH RELINKING FOR BROADCAST SCHEDULINGCommander, Clayton W., Butenko, Sergiy I., Pardalos, Panos M., Oliveira, Carlos A.S. 10 1900 (has links)
International Telemetering Conference Proceedings / October 1821, 2004 / Town & Country Resort, San Diego, California / The Broadcast Scheduling Problem (BSP) is a well known NPcomplete problem that arises in the study of wireless networks. In the BSP, a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. The objective is a collision free transmission schedule with the minimum number of TDMA slots and maximal slot utilization. Such a schedule will minimize the total system delay. We present variations of a Greedy Randomized Adaptive Search Procedure (GRASP) for the BSP. Pathrelinking, a postoptimization strategy is applied. Also, a reactivity method is used to balance GRASP parameters. Numerical results of our research are reported and compared with other heuristics from the literature.

Page generated in 0.0969 seconds