No description available.

In this thesis, first we propose a new approach to solve Semi Infinite Linear Optimization Problems (SILP). The new algorithm uses the idea of adding violated cut or cuts at each iteration. Our proposed algorithm distinguishes itself from Luo, Roos, and Terlaky's logarithmic barrier decomposition method, in three aspects: First, the violated cuts are added at their original locations. Second, we extend the analysis to the case where multiple violated cuts are added simultaneously, instead of adding only one constraint at a time. Finally, at each iteration we update the barrier parameter and the feasible set in the same step. In terms of complexity, we also show that a good approximation of an optimal solution will be guaranteed after finite number of iterations. Our focus in this thesis is mainly on the implementation of our algorithm to approximate an optimal solution of the SILP. Our numerical experiences show that unlike other SILP solvers which are suffering from the lack of accuracy, our algorithm can reach high accuracy in a competitive time. We discuss the linear algebra involved in efficient implementation and describe the software that was developed. Our test problem set includes large scale second order conic optimization problems. / Thesis / Master of Applied Science (MASc)

Le développement de structures de réseau efficaces pour le transport de marchandises est fondamental sur le marché mondial actuel. Les demandes doivent être traitées rapidement, répondre aux besoins des clients dans les meilleurs délais, les congestions et les retards doivent être minimisés, les émissions de CO2 doivent être contrôlés et des coûts de transport moins élevés doivent être proposés aux clients. La structure hub-and-spoke est un modèle de réseau courant utilisé à la fois dans le transport régional comme dans le transport intercontinental, permettant une économie d'échelle grâce aux consolidations opérées au niveau des noeuds hub. Mais, les retards, les congestions et les longs délais de livraison sont des inconvénients de ce type de réseau. Dans cette thèse, un nouveau concept, "sub-hub", est ajouté à la structure du réseau classique hub-and-spoke. Dans les modèles de réseau proposés, une économie d'échelle et des chemins alternatifs plus courts sont mis en oeuvre, en minimisant ainsi le coût de transport et le délai de livraison. Le sub-hub est vu comme un point de connexion entre deux routes distinctes de régions voisines. Des transbordements sans passer par les noeuds hub sont possibles au niveau des sub-hubs. Des congestions peuvent ainsi être évitées et, par conséquent, les retards associés sont ainsi minimisés. Quatre modèles de programmation linéaire en nombres entiers binaires du problème de la localisation de hubs et de routage sont développés dans cette thèse. Des réseaux avec sub-hub et des réseaux sans sub-hub prenant en compte des routes circulaires entre hubs ou des connexions directes entre hubs sont ainsi comparées. Ces modèles sont composés de quatre sous-problèmes (localisation, allocation, conception de service et routage) qui rendent complexe la recherche de solutions. Une approche cutting plane est testée pour résoudre de petites instances de problème tandis qu'une recherche à voisinage variable avec décomposition (VNDS) composée de méthodes exactes (matheuristic) a été développée pour résoudre de grandes instances. Le VNDS mis en oeuvre, explore chaque sous-problème avec différents opérateurs. Des gains importants dans la fonction objective sont observés par les modèles avec sub-hub confirmant ainsi le développement de réseaux plus compétitifs. / The development of efficient network structures for freight transport is a major concern for the current global market. Demands need to be quickly transported and should also meet the customer needs in a short period of time. Traffic congestions and delays must be minimized, since CO2 emissions must be controlled and affordable transport costs have to be offered to customers. Hub-and-spoke structure is a current network model used by both regional and intercontinental transportation, which offers an economy of scale for aggregated demands inside hub nodes. However, delays, traffic congestions and long delivery time are drawbacks from this kind of network. In this thesis, a new concept, which is called "sub-hub", is proposed to the classic hub-and-spoke network structure. In the proposed network models, economy of scale and shorter alternative paths are implemented, thus minimizing the transport cost and delivery time. The sub-hub proposal can be viewed as a connection point between two routes from distinct and close regions. Transshipments without the need to pass through hub nodes are possible inside sub-hubs. This way, congestions can be avoided and, consequently, delays are minimized. Four binary integer linear programming models for hub location and routing problem were developed in this thesis. Networks with sub-hub and networks without sub-hub taking into account circular hub routes or direct connections between hubs are compared. These models are composed of four sub-problems (location, allocation, service design and routing), which hinders the solution. A cutting plane approach was used to solve small instances of problem, while a Variable Neighborhood Decomposition Search (VNDS) composed of exact methods (matheuristic) was developed to solve large instances. The VNDS was used to explore each sub-problem by different operators. Major benefits are provided by models with sub-hub, thus promoting the development of more competitive networks.

In this dissertation, a finitely convergent disjunctive programming procedure, the Convex Hull Tree (CHT) algorithm, is proposed to obtain the convex hull of a general mixed–integer linear program with bounded integer variables. The CHT algorithm constructs a linear program that has the same optimal solution as the associated mixed-integer linear program. The standard notion of sequential cutting planes is then combined with ideasunderlying the CHT algorithm to help guide the choice of disjunctions to use within a new cutting plane method, the Cutting Plane Tree (CPT) algorithm. We show that the CPT algorithm converges to an integer optimal solution of the general mixed-integer linear program with bounded integer variables in finitely many steps. We also enhance the CPT algorithm with several techniques including a “round-of-cuts” approach and an iterative method for solving the cut generation linear program (CGLP). Two normalization constraints are discussed in detail for solving the CGLP. For moderately sized instances, our study shows that the CPT algorithm provides significant gap closures with a pure cutting plane method.

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal's attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately. To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm. It was found that valid cuts generated using the analytic center cutting plane method reduce the number of times the integer Benders master problem is solved and therefore reduce the computational time. It was also found that the combinatorial Benders reduces the complexity of the integer master problem by reducing the number of integer variables in it. The valid cuts generated within the nested Benders algorithm proved to be beneficial in reducing the number of times the combinatorial Benders master problem is solved and in reducing the computational time that the overall algorithm takes. Over 110 instances of the UMTS/W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality.

The single-row facility layout problem (SRFLP) is concerned with finding the optimal linear placement of n departments with different lengths in a straight line. It is typically achieved by minimizing the cost associated with the interactions between the departments. The semidefinite programming (SDP) relaxation model that incorporates cutting planes proposed recently by Anjos, Kennings, and Vannelli (AKV) was considered a breakthrough in the field. This thesis presents a new SDP model AKV' and compares the two relaxations. The AKV' is largely based on the previous model, but it reduces the number of linear constraints from O(n³) to O(n²). Therefore, it reduces the computing time at the expense of a slightly weaker lower bound. However, AKV' is observed to pay off as the instance size increases. By examining the gap for both the AKV and AKV' relaxations, we notice that both relaxations generate very small gaps at the root node, which demonstrates the effectiveness of the relaxations. Six different strategies are presented to separate the cutting planes for the medium-sized SRFLP. In combination with the two SDP relaxations, we compare the six strategies using three instances of different characteristics. An overall best strategy is deduced from the computational results, but the best choice of relaxations and the best number of cuts added at each iteration changes depending on the characteristics of the instances. Two new cutting plane strategies are proposed for large instances. This allows the solution to optimality of new instances with 36 departments, which is higher than previously published results in literature. We also briefly point out how the computing time can vary greatly between different sets of data of the same size due to the characteristics of the department lengths.

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal's attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately. To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm. It was found that valid cuts generated using the analytic center cutting plane method reduce the number of times the integer Benders master problem is solved and therefore reduce the computational time. It was also found that the combinatorial Benders reduces the complexity of the integer master problem by reducing the number of integer variables in it. The valid cuts generated within the nested Benders algorithm proved to be beneficial in reducing the number of times the combinatorial Benders master problem is solved and in reducing the computational time that the overall algorithm takes. Over 110 instances of the UMTS/W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality.

The single-row facility layout problem (SRFLP) is concerned with finding the optimal linear placement of n departments with different lengths in a straight line. It is typically achieved by minimizing the cost associated with the interactions between the departments. The semidefinite programming (SDP) relaxation model that incorporates cutting planes proposed recently by Anjos, Kennings, and Vannelli (AKV) was considered a breakthrough in the field. This thesis presents a new SDP model AKV' and compares the two relaxations. The AKV' is largely based on the previous model, but it reduces the number of linear constraints from O(n³) to O(n²). Therefore, it reduces the computing time at the expense of a slightly weaker lower bound. However, AKV' is observed to pay off as the instance size increases. By examining the gap for both the AKV and AKV' relaxations, we notice that both relaxations generate very small gaps at the root node, which demonstrates the effectiveness of the relaxations. Six different strategies are presented to separate the cutting planes for the medium-sized SRFLP. In combination with the two SDP relaxations, we compare the six strategies using three instances of different characteristics. An overall best strategy is deduced from the computational results, but the best choice of relaxations and the best number of cuts added at each iteration changes depending on the characteristics of the instances. Two new cutting plane strategies are proposed for large instances. This allows the solution to optimality of new instances with 36 departments, which is higher than previously published results in literature. We also briefly point out how the computing time can vary greatly between different sets of data of the same size due to the characteristics of the department lengths.

Many tasks in Natural Language Processing (NLP) require us to predict a relational structure over entities. For example, in Semantic Role Labelling we try to predict the ’semantic role’ relation between a predicate verb and its argument constituents. Often NLP tasks not only involve related entities but also relations that are stochastically correlated. For instance, in Semantic Role Labelling the roles of different constituents are correlated: we cannot assign the agent role to one constituent if we have already assigned this role to another. Statistical Relational Learning (also known as First Order Probabilistic Logic) allows us to capture the aforementioned nature of NLP tasks because it is based on the notions of entities, relations and stochastic correlations between relationships. It is therefore often straightforward to formulate an NLP task using a First Order probabilistic language such as Markov Logic. However, the generality of this approach comes at a price: the process of finding the relational structure with highest probability, also known as maximum a posteriori (MAP) inference, is often inefficient, if not intractable. In this work we seek to improve the efficiency of MAP inference for Statistical Relational Learning. We propose a meta-algorithm, namely Cutting Plane Inference (CPI), that iteratively solves small subproblems of the original problem using any existing MAP technique and inspects parts of the problem that are not yet included in the current subproblem but could potentially lead to an improved solution. Our hypothesis is that this algorithm can dramatically improve the efficiency of existing methods while remaining at least as accurate. We frame the algorithm in Markov Logic, a language that combines First Order Logic and Markov Networks. Our hypothesis is evaluated using two tasks: Semantic Role Labelling and Entity Resolution. It is shown that the proposed algorithm improves the efficiency of two existing methods by two orders of magnitude and leads an approximate method to more probable solutions. We also give show that CPI, at convergence, is guaranteed to be at least as accurate as the method used within its inner loop. Another core contribution of this work is a theoretic and empirical analysis of the boundary conditions of Cutting Plane Inference. We describe cases when Cutting Plane Inference will definitely be difficult (because it instantiates large networks or needs many iterations) and when it will be easy (because it instantiates small networks and needs only few iterations).

[pt] Este trabalho consiste da aplicação de métodos de planos de corte (euclideano acelerado e cortes disjuntivos) na solução de problemas de programação inteira pura do tipo 0- 1 e suas especializações para o problemas de particionamento, quando combinados com técnicas de penalidades para fixação de variáveis. Desenvolve-se um estudo de técnicas de penalidades, que permitem fixar variáveis a valores inteiros a partir da solução ótima da relaxação linear do problema inteiro. As variáveis fixadas são eliminadas do problema e este é reescrito, tendo suas dimensões originais reduzidas. Sugerem-se melhorias no cálculo destas penalidades, levando-se em conta a estrutura particular do problema de particionamento. Finalmente, propõe-se um novo enfoque para a solução de problemas de particionamento: um algoritmo de planos de corte que utiliza técnicas de penalidades, com a finalidade de acelerar a convergência dos métodos puros de planos de corte e de reduzir os problemas por estes apresentados. Resultados computacionais são apresentados, comparando-se o desempenho (i) do algoritmo euclideano acelerado, (ii) do algoritmo de cortes disjuntivos e (iii) do algoritmo de cortes disjuntivos utilizando-se técnicas de penalidades. Para este último algoritmo, são comparados os resultados obtidos utilizando-se técnicas de penalidades genéricas para problemas inteiros do tipo 0-1 e as melhorias destas penalidades, especificas para problemas de particionamento. Considerando-se o problemas de particionamento e as melhorias propostas no cálculo de penalidades, mostra-se que é, freqüentemente, possível fixar um maior número de variáveis ou até mesmo resolver-se diretamente o problema 0-1 original. Em alguns casos, ao aplicar-se o algoritmo de planos de corte com técnicas de penalidades não só pode- se acelerar a convergência, como também superar os problemas de degenerescência dual e erros por arredondamento apresentados pelos algoritmos puros de plano de corte. / [en] This work consists on the application of cutting plane techniques (accelerated euclidean algorithm and disjunctive cuts) for solving pure 0-1 integer problems and their specializations for the set partitioning problem, when combined to penalty techniques for fixing variables. A study on penalty techniques, which allows the fixation of variables to integer values, is also developed. These penalties are directly derived from the optimal tableau nof the linear relaxation of the integer problem. The variables fixed due to penalties are eliminated and the problem is reformulated, having its initial dimensions reduced. Some improvements on the evaluation of penalties are suggested, taking into account the special structure of the set partitioning problem. Finally, a new approach to the solution of set partitioning problems is proposed: a cutting plane algorithm which uses penalty techniques, in order to accelerate the convergence of pure cutting plane methods and overcome the problems arising from their use. Computational results are shown, allowing to compare the performance of (i) the accelerated euclidean algorithm, (ii) the disjunctive cut algorithm and (iii) the last one combined with penalty techniques. For the latter, the results obained by the use of generic penalties for 0-1 integer programs are compared with those obtained by the use of the improved penalties for ser partitioning problems. Taking into account set partitioninng problems and the improvements proposed for the evaluation of penalties, it is shown that very often it is possible to fix more variables to integer values and even to solve directly the original 0-1 problem. For some cases, by applying the cutting plane algorithm together with penalties, it is possible to accelerate the convergence and overcome dual degeneracy and round-off errors arising from the use of pure cutting plane algorithms.