Spelling suggestions: "subject:"[een] BRANCH AND PRICE"" "subject:"[enn] BRANCH AND PRICE""
11 |
A branch-and-price algorith, for a compressor scheduling problemFriske, Marcelo Wuttig January 2016 (has links)
O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. / This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time.
|
12 |
Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problemSachdeva, Sandeep 12 April 2006 (has links)
We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
|
13 |
Vers un outil d’aide à la planification et à l’ordonnancement des blocs opératoiresFEI, Hongying 17 March 2006 (has links)
Résumé
Dans cette thèse, nous étudions la gestion des blocs opératoires, et plus particulièrement la planification et l’ordonnancement de ces blocs. Le choix d’études de ce secteur hospitalier est lié au fait qu’il est réputé comme un lieu hautement stratégique dans un établissement hospitalier, surtout en terme de coûts. Il est dès lors utile de s’intéresser à l’optimisation de l’utilisation des ressources hospitalières. Etant donné que l’optimisation du fonctionnement des blocs opératoires est un problème vaste et complexe, nous nous focalisons sur deux sous-problèmes déjà réputés difficiles : la planification et l’ordonnancement des interventions chirurgicales. Ce sont des problèmes centrés sur la programmation opératoire et dont l’objectif est d’obtenir un programme opératoire réalisable et efficace du bloc.
Les problèmes de planification sont premièrement formalisés comme des modèles mathématiques en nombres entiers et puis résolus par des procédures heuristiques et par un « Branch-and-Price » basés sur la génération de colonnes qui est utilisée pour résoudre les relaxations linéaires des modèles concernés afin de trouver les bornes inférieures. Les modèles d’ordonnancement sont traités comme des variantes de modèles de « flow shop » hybride à deux étages et résolus par des algorithmes génétiques hybrides. Finalement, nos modèles ont été testés et validés sur un cas réel.
ABSTRACT
This thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to make a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At first the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price one. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case.
|
14 |
Locations On A Line And Generalization To The Dynamic P-mediansGuden, Huseyin 01 September 2012 (has links) (PDF)
This study deals with four location problems. The first problem is a brand new location problem on a line and considers the location decisions for depots and quarries in a highway construction project. We develop optimal solution properties of the problem. Using these properties, a dynamic programming algorithm is proposed. The second problem is also a brand new dynamic location problem on a line and locates concrete batching mobile and immobile facilities for a railroad construction project. We develop two mixed integer models to solve the problem. For solving large size problems, we propose a heuristic. Performances of models and the heuristic are tested on randomly generated instances plus a case study data and results are presented. The third problem is a generalization of the second problem to network locations. It is a dynamic version of the well known p-median problem and incorporates mobile facilities. The problem is to locate predetermined number of mobile and immobile facilities over a planning horizon such that sum of facility movement and allocation costs is minimized. Three constructive heuristics and a branch-and-price algorithm are proposed. Performances of these solution procedures are tested on randomly generated instances and results are presented. In the fourth problem we consider a special case of the third problem, allowing only conventional facilities. The algorithm for the third problem is improved so that generating columns and solving a mixed integer model are used repetitively. Performance of the algorithm is tested on randomly generated instances and results are presented.
|
15 |
Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problemSachdeva, Sandeep 12 April 2006 (has links)
We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.
|
16 |
Prioritization via stochastic optimizationKoc, Ali 31 January 2011 (has links)
We take a novel perspective on real-life decision making problems involving binary activity-selection decisions that compete for scarce resources. The current literature in operations research approaches these problems by forming an optimal portfolio of activities that meets the specified resource constraints. However, often practitioners in industry and government do not take the optimal-portfolio approach. Instead, they form a rank-ordered list of activities and
select those that have the highest priority.
The academic literature tends to discredit such ranking schemes because they ignore dependencies among the activities. Practitioners, on the other hand, sometimes discredit the optimal-portfolio approach because if the
problem parameters change, the set of activities that was once optimal no longer remains optimal. Even worse, the new optimal set of activities may exclude some of the previously optimal activities, which they may have already
selected. Our approach takes both viewpoints into account. We rank activities considering both the uncertainty in the problem parameters and the optimal portfolio that will be obtained once the uncertainty is revealed.
We use stochastic integer programming as a modeling framework. We develop several mathematical formulations and discuss their relative merits,
comparing them theoretically and computationally. We also develop cutting planes for these formulations to improve computation times. To be able to
handle larger real-life problem instances, we develop parallel branch-and-price algorithms for a capital budgeting application. Specifically, we construct a
column-based reformulation, develop two branching strategies and a tabu search-based primal heuristic, propose two parallelization schemes, and compare these schemes on parallel computing environments using commercial and open-source software.
We give applications of prioritization in facility location and capital budgeting problems. In the latter application, we rank maintenance and capital-improvement projects at the South Texas Project Nuclear Operating Company, a two-unit nuclear power plant in Wadsworth, Texas. We compare our approach with several ad hoc ranking schemes similar to those used in
practice. / text
|
17 |
A branch-and-price algorith, for a compressor scheduling problemFriske, Marcelo Wuttig January 2016 (has links)
O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. / This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time.
|
18 |
Branch & price for the virtual network embedding problem / Branch & price para o problema de mapeamento de redes virtuaisMoura, Leonardo Fernando dos Santos January 2015 (has links)
Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX. / Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.
|
19 |
A branch-and-price algorith, for a compressor scheduling problemFriske, Marcelo Wuttig January 2016 (has links)
O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. / This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time.
|
20 |
Branch & price for the virtual network embedding problem / Branch & price para o problema de mapeamento de redes virtuaisMoura, Leonardo Fernando dos Santos January 2015 (has links)
Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX. / Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.
|
Page generated in 0.0371 seconds