Search

International audience; In this paper, we propose graph-based models for several vehicle routing problems with intermediate stops: the capacitated multi-trip vehicle routing problem with time windows, the multi-depot vehicle routing problem with inter-depot routes, the arc routing problem with intermediate facilities under capacity and length restrictions and the green vehicle routing problem. In these models, the set of feasible routes is represented by a set of resource constrained paths in one or several graphs. Intermediate stops are supported by the possibility to define negative resource consumption for some arcs. The models that we propose are then solved by VRPSolver, which implements a generic branch-cut-and-price exact algorithm. Thus, a simple parameterization enables us to use several state-of-the-art algorithmic components: automatic stabilization by dual price smoothing, limited-memory rank-1 cuts, reduced cost-based arc elimination, enumeration of elementary routes, and hierarchical strong branching. For each problem, we numerically compare the proposed methodology with the best exact approach found in the literature. State-of-the-art computational results were obtained for all problems except one.

The Cumulative Capacitated Vehicle Routing Problem is a variant of the classic routing problem in which the objective function is to minimize the sum of arrival times to customers. This article proposes a model for the problem that uses position indexes in order to calculate the contribution of the travel time of an edge to the arrival times of the remaining customers on a route. The model is implemented and solved by the branch-cut-and-price (BCP) algorithm in the VRPSolver package. Computational experiments indicate that the proposed BCP model is superior to the literature, being able to solve many open instances. Good results were also obtained for the Multi-Depot variant of the problem.

The knapsack problem with conflicting items arises in several real-world applications. We propose a family of strong cutting planes and prove that a subfamily of these cuts can be facet-defining. Computational experiments show that the proposed cuts are very effective in reducing integrality gaps, providing dual bounds up to 78% tighter than formulations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts.

Neste artigo, o problema de roteamento de veículos com janelas de tempo é abordado, como forma de incorporar características de dinamicidade da cadeia logística de entregas expressas, explorando aspectos teóricos que melhor definem o problema e suas instâncias. O problema consiste em determinar rotas de custo mínimo que devem ser executadas por uma frota de veículos respeitando suas capacidades e as janelas de tempo de entregas de cada cliente. Uma estratégia que utiliza o método de Branch-Cut-and-Price através da ferramenta VRPsolver foi aplicada em dois conjuntos de instâncias, sendo a primeira as instâncias clássicas artificiais de Solomon e, a segunda, instâncias reais brasileiras adaptadas do benchmark loggiBUD.

We consider the shortest path problem with resource constraints arising as a subproblem in state-of-the-art branch-cut-and-price algorithms for vehicle routing problems. We propose a variant of the bidirectional label-correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. This organization of labels helps to significantly decrease the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance-constrained vehicle routing problem, including multidepot and site-dependent variants, on the vehicle routing problem with time windows, and on the “nightmare” instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved, and many instances could be solved for the first time.

International audience; In this paper, we are interested in the exact solution of the vehicle routing problem with back-hauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first of them follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing sub-problems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing benchmark instances with up to 200 customers, many of them for the first time. It is observed that the approach involving two pricing subproblems is more efficient computationally than the traditional one. Moreover, new instances are also proposed for which we provide tight bounds. Also, we provide results for benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows.

Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best existing VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, path enumeration, and rounded capacity cuts; all generalized through the new concepts of “packing set” and “elementarity set”. The concepts are also used to derive a branching rule based on accumulated resource consumption and to generalize the Ryan and Foster branching rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

We consider a variant of the Travelling Salesman Problem (TSP), the Multiple Steiner TSP with Order constraints (MSTSPO). Consider a weighted undirected graph and a set of salesmen, and each salesman is associated with a set of compulsory vertices to visit, called terminals. The MSTSPO consists in finding a minimum-cost subgraph containing for each salesman a tour going in a specified order through its terminals. Along with its importance from a theoretical point of view, the problem is also challenging in practice since it has applications in telecommunication networks. We show that the problem is NP-hard even for a single salesman and propose integer programming formulations. We then devise both Branch-and-Cut and Branch-and-Price algorithms to solve the problem. The extensive computational results are presented, showing the efficiency of our algorithms.

Este paper tem o objetivo de apresentar a metodologia e os resultados alcancados pelo Mine to Plant na mina de cobre da Vale Salobo. O Mine to Plant esta baseado no conceito de que melhorias de fragmentacao por desmonte de rochas tem efeito positivo sobre a performance da planta de beneficiamento. A Vale iniciou as operacoes do Salobo I (12 Mtpa) em Q2-2012, em Q2-2014 iniciou-se a operacao do Salobo II (24Mtpa). Em Q1-2015 iniciou-se a primeira fase dos trabalhos de Mine to Plant (Ano #1) e Q1-2016 a segunda fase do projeto (Ano # 2) Mesmo com a complexidade das analises tecnicas em se determinar o impacto correspondente para cada uma das iniciativas de melhorias na operacao de desmonte realizadas em paralelo com start up da planta de beneficiamento, durante o Ano # 1, o departamento de mina e planta implementou a metodologia com sucesso na Vale Salobo. Este paper apresenta os resultados de aumento de tratamento (tph) da segunda fase de trabalho, em cada uma das etapas de britagem primaria e secundaria, Moagem de rolos HPGRs e moagem de bolas, bem como a comparacao dos resultados de KPIs da linha base, ano # 1 e ano # 2. As melhorias nas tecnicas de desmonte, dos controles operacionais, e uso de explosivos mais energeticos bem como uso de sistemas eletronicos de iniciacao permitiram uma reducao do top size do ROM, P80 e P50 e consequentemente reducao dos eventos de paradas na britagem primaria por blocos e engaiolamento. Nesta segunda etapa do trabalho, ultimos12 meses, manteve-se as melhorias alcancadas nas etapas de britagens e buscou um incremento na participacao de finos atraves de desmontes com alta razao de carga e explosivo mais energeticos. Foi possivel determinar que o desmonte aumentou o tratamento da britagem primaria em 20%, em 19% a britagem secundaria e 2,5% no circuito de HPGR e moagem de bolas.

The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing out similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies are suitable for each alternative and their pricing complexities. That analysis is used to justify key decisions on constructing a new branch-cut-and-price algorithm that combines several features picked from the capacitated arc routing literature with some features adapted from the most successful recent algorithms for node routing. The computational experiments show that the resulting algorithm is indeed effective and can solve almost all open instances from the classical benchmark sets.

The Workforce Problem (WP) can be classified in three categories: strategic planning, tactical planning and operational planning. The WP can be applied to any type of company, for example, in Operation and Maintenance (O&M) management. In recent years, O&M's WP has been thoroughly analysed in the electricity sector by electricity distributors such as Copel, Celpe, Cemig, AES Sul and Elektro, aiming to optimize the attendance of events. The main goal of this work is to present the state of the art of WP focused on power utilities, as well as some topics related to power distribution planning at strategic, tactical and operational levels. The survey reveals that most studies of WP in electrical distribution utilities analyses operational planning.

Background and aim This study aimed to describe the clinical, genetic, and epidemiological features of Charcot-Marie-Tooth disease (CMT) in Brazilian patients from a tertiary center, and to compare our data with previously published findings. Methods This retrospective observational study conducted between February 2015 and July 2020 evaluated 503 patients (94 families and 192 unrelated individuals), diagnosed with CMT. Clinical and neurophysiological data were obtained from electronic medical records and blood samples were used for genetic analyses. Multiplex ligation-dependent probe amplification was used to assess duplications/deletions in PMP22. Sanger sequencing of GJB1 was performed in cases of suspected demyelinating CMT. Targeted gene panel sequencing was used for the remaining negative demyelinating cases and all axonal CMT cases. Results The first decade of life was the most common period of disease onset. In all, 353 patients had demyelinating CMT, 39 had intermediate CMT, and 111 had axonal CMT. Pathogenic or likely pathogenic variants were identified in 197 index cases. The most common causative genes among probands were PMP22 (duplication) (n=116, 58.88%), GJB1 (n=23, 11.67%), MFN2 (n=12, 6.09%), GDAP1 (n=7, 3.55%), MPZ (n=6, 3.05%), PMP22 (point mutation) (n=6, 3.05%), NEFL (n=3, 1.52%), SBF2 (n=3, 1.52%), and SH3TC2 (n=3, 1.52%). Other identified variants were ≤1% of index cases. Interpretation This study provides further data on the frequency of CMT subtypes in a Brazilian clinical-based population and highlights the importance of rarer and previously undiagnosed variants in clinical practice. This article is protected by copyright. All rights reserved.

Christofides and Hadjiconstantinou (1995) introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably obtains the optimal weights. In order to obtain even better upper bounds, that algorithm is generalized into Algorithm X2 for obtaining optimal two-dimensional item weights. We also present a full hybrid method, called Algorithm X2D, that computes those strong upper bounds but also provides feasible solutions obtained by: (1) exploring the suboptimal solutions hidden in the dynamic programming matrices; (2) performing a number of iterations of a GRASP based primal heuristic; and (3) executing X2H, an adaptation of Algorithm X2 to transform it into a primal heuristic. Extensive experiments with instances from the literature and on newly proposed instances, for both variants with and without item rotation, show that X2D can consistently deliver high-quality solutions and sharp upper bounds. In many cases the provided solutions are certified to be optimal.

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary n -row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.

The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut BPC. First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers. The online appendix is available at https://doi.org/10.1287/ijoc.2016.0744 .

Pecin etal. (2016) introduced a limited memory technique that allows an efficient use of Rank-1 cuts in the Set Partitioning Formulation of Vehicle Routing Problems, motivating a deeper investigation of those cuts. This work presents a computational polyhedral study that determines the best possible sets of multipliers for cuts with up to 5 rows. Experiments with CVRP instances show that the new multipliers lead to significantly improved dual bounds and contributes decisively for solving an open instance with 420 customers.

The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suffer from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too artificial; (iii) are too homogeneous, not covering the wide range of characteristics found in real applications. We propose a new set of 100 instances ranging from 100 to 1000 customers, designed in order to provide a more comprehensive and balanced experimental setting. Moreover, the same generating scheme was also used to provide an extended benchmark of 600 instances. In addition to having a greater discriminating ability to identify “which algorithm is better”, these new benchmarks should also allow for a deeper statistical analysis of the performance of an algorithm. In particular, they will enable one to investigate how the characteristics of an instance affect its performance. We report such an analysis on state-of-the-art exact and heuristic methods.

The paper deals with a variant of the Traveling Saleman Problem (TSP), called the Multiple Steiner TSP with Order Constraints (MSTSPOC). Consider an undirected weighted graph, and a set of salesmen such that with each salesman is associated a set of ordered terminals. The MSTSPOC consists in finding a minimum-cost subgraph containing for each salesman a tour going in order through its terminals. We propose an ILP formulation for the problem, study the associated polytope and investigate the facial aspects of the basic constraints. We further identify new families of valid inequalities. Some computational results are also presented.

This paper addresses the problem of maintenance facilities (depot) location in electric power distribution systems with a focus on strategic planning. Power interruptions can be harmful for both society and distribution companies. Determining the optimal number and sites of depot location to handle power interruptions in the long term can improve the quality of service. Through a good depot location, the distance from depots to work orders (WO) is minimized, operational costs can be minimized and customer interruption duration is reduced, which is a good indicator of the reliability of the system. The problem was solved by a Particle Swarm Optimization (PSO) algorithm and a Mixed Integer Linear Programming (MILP) model. In addition to the real instance, some synthetic ones were generated to compare both approaches in large-sized scenarios. The computational results show that the two approaches are complementary strategies, being presented the scenarios where each proposal could provide better results.

In this paper we study a network design problem that consists in finding a minimum weight subgraph containing solutions for multiple Steiner Traveling Salesman Problems with Order constraints. We propose a layered compact ILP formulation for the problem. Experimental results show that it is reasonably effective and can solve to optimality medium-sized instances. Lage-scale instances are more difficult, and does not reach optimal solutions within a time limit of 3 hours. In order to improve our formulation, we investigate valid inequalities efficiency using a column-generation-based approach.

The best performing exact algorithms for the capacitated vehicle routing problem developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the subset row cuts. This work introduces a technique for greatly reducing the impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed branch-cut-and-price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.

The Traveling Salesperson Problem with Hotel Selection (TSPHS) is an extension of the classic Traveling Salesperson Problem that has only recently been introduced in the literature, where there is a daily travel limit such that several trips might be necessary to visit all clients and there is a set of available hotels for the salesperson to stay in between trips. The TSPHS not only presents an interesting optimization challenge, but also has a strong relevance in real world applications. Current approaches focus mainly in meta-heuristic techniques. The lack of a robust exact algorithm limits the extent to which this problem can be studied. This thesis presents a set partitioning Integer Programing formulation and proposes a branch-cut-and-price algorithm, where the pricing subproblem is solved through a labeling algorithm. Subtour elimination constraints, 2-Path and Subset Row Cuts are separated. Several instances of the literature of up to 225 clients are solved to optimality and a new set of 240 benchmark instances is presented where optimal solutions are obtained for instances of up to 100 clients

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best recent VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, and route enumeration; all generalized through the new concept of “packing set”. This concept is also used to derive a new branch rule based on accumulated resource consumption and to generalize the Ryan and Foster branch rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best existing specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

International audience; This work presents the application of branch-and-price approaches to the auto- matic version of the Software Clustering Problem. To tackle this problem, we apply the Dantzig-Wolfe decomposition to a formulation from literature. Given this, we present two Column Generation (CG) approaches to solve the linear programming relaxation of the resulting reformulation: the standard CG approach, and a new approach, which we call Staged Column Generation (SCG). Also, we propose a modification to the pricing subproblem that allows to add multiple columns at each iteration of the CG. We test our algorithms in a set of 45 instances from the literature. The proposed approaches were able to improve the literature results solving all these instances to optimality. Furthermore, the SCG approach presented a considerable performance improvement regarding computational time, number of iterations and generated columns when compared with the standard CG as the size of the instances grows.

In this paper, we address the Unsplittable Non-Additive Capacitated Network Design problem, a variant of the Capacitated Network Design problem where the flow of each commodity cannot be split, even between two facilities installed on the same link. We propose a compact formulation and an aggregated formulation for the problem. The latter requires additional inequalities from considering each individual arc-set. Instead of studying those particular polyhedra, we consider a much more general object, the unitary step monotonically increasing set function polyhedra, and identify some families of facets. The inequalities that are obtained by specializing those facets to the Bin Packing function are separated in a Branch-and-Cut for the problem. Several series of experiments are conducted on random and realistic instances to give an insight on the efficiency of the introduced valid inequalities. HighlightsWe give two ILP formulations for the UNACND problem.We introduce polyhedra associated with a general class of functions.We provide two classes of facets that are valid for all considered functions.We devise a Branch-and-Cut algorithm embedding both classes of inequalities.Our approach gives promising results and shows the efficiency of our inequalities.

The societal and economic impact of ischemic stroke in young adults is considerable. The etiological investigation of ischemic stroke in this population is also challenging. To describe the characteristics of young patients with ischemic stroke admitted to a neurological rehabilitation program in Brazil. This transversal retrospective study analyzed data from the electronic health records of 134 patients aged 18 to 45 years with ischemic stroke admitted from 2008 to 2012. The average patient age at the time of ictus was 33 years; 56% of the subjects were female, and 29.3% had undetermined etiologies of stroke, on the basis of both TOAST and SSS TOAST criteria. Further, 48.7% of the subjects had a known vascular risk factor, which was arterial hypertension in most cases. The results of thrombophilia testing were positive in 13.7% of patients, but in only 3.7% of patients, thrombophilia was determined to be the causal mechanism of the stroke. There was a significant association between thrombophilia and patent foramen ovale, but no significant association was found between thrombophilia and arterial dissection. Among the patients with artery dissections, 46% had a history of trauma, which was statistically significant. Etiological diagnosis of stroke in the young is challenging for clinicians. Hence, a more effective classification scheme, better investigative mechanisms, and correct determination of causal associations in ischemic stroke are needed. Thrombophilia screening should be performed in the presence of relevant clinical signs and/or family history.

We consider the Capacitated Multi-Layer Network Design with Unsplittable demands (CMLND-U) problem. Given a two-layer network and a set of traffic demands, this problem consists in installing minimum cost capacities on the upper layer so that each demand is routed along a unique “virtual” path (even using a unique capacity on each link) in this layer, and each installed capacity is in turn associated a “physical” path in the lower layer. This particular hierarchical and unsplittable requirement for routing arises in the design of optical networks, including optical OFDM based networks. In this paper, we give an ILP formulation to the CMLND-U problem and we take advantage of its sub-problems to provide a partial characterization of the CMLND-U polytope including several families of facets. Based on this polyhedral study, we develop a Branch-and-Cut algorithm for the problem and show its effectiveness though a set of experiments, conducted on SNDlib-derived instances and also on real instances.

Oil tankers play a fundamental role in every offshore petroleum supply chain and due to its high price, it is essential to optimize its use. Since this optimization requires handling detailed operational aspects, complete optimization models are typically intractable. Thus, a usual approach is to solve a tactical level model prior to optimize the operational details. In this case, it is desirable that tactical models are as precise as possible to avoid too severe adjustments in the next optimization level. In this paper, we study tactical models for a crude oil transportation problem by tankers. We did our work on the top of a previous paper found in the literature. The previous model considers inventory capacities and discrete lot sizes to be transported, aiming to meet given demands over a finite time horizon. We compare several formulations for this model using 50 instances from the literature and proposing 25 new harder ones. A column generation-based heuristic is also proposed to find good feasible solutions with less computational burden than the heuristics of the commercial solver used.

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.

BACKGROUND The relationship between renal dysfunction and mortality after myocardial infarction (MI) has been demonstrated in patients with reduced ejection fraction. The importance of diastolic dysfunction in this scenario is unknown. METHODS We studied 749 patients with acute MI who were evaluated within 24 hours of symptom onset. The Modification of Diet in Renal Disease equation was used to calculate the estimated glomerular filtration rate (eGFR). Preserved and depressed renal functions were defined as eGFR >60 and

Increasingly, clusters of servers have been deployed in large data centers to support the development and implementation of many kinds of services, having distinct workload demands that vary over time, in a scalable and efficient computing environment. Emerging trends are utility/cloud computing platforms, where many network services, implemented and supported using server virtualization techniques, are hosted on a shared cluster infrastructure of physical servers. The energy consumed to maintain these large server clusters became a very important concern, which in turn, requires major investigation of optimization techniques to improve the energy efficiency of their computing infrastructure. In this work, we propose an efficient approach to solve a relevant cluster optimization problem which, in practice, can be used as an embedded module to implement an integrated power and performance management solution in a real server cluster. The optimization approach simultaneously deals with (i) CPU power-saving techniques combined with server switching on/off mechanisms, (ii) the case of server heterogeneity, (iii) virtualized server environments, (iv) an efficient optimization method, which is based on column generation techniques. The key aspects of our approach are the basis on rigorous and robust optimization techniques, given by high quality solutions in short amount of processing time, and experimental results on the cluster configuration problem for large-scale heterogeneous server clusters that can make use of virtualization techniques.

This work proposes a Branch-cut-and-price (BCP) approach for the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We also deal with a particular case of the VRPSPD, known as the Vehicle Routing Problem with Mixed Pickup and Delivery. The BCP algorithm was tested in well-known benchmark instances involving up to 200 customers. Four instances were solved for the first time and some LBs were improved.

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.

Although opening an occluded infarct-related artery24 hours after myocardial infarction in stable patients in the Occluded Artery Trial (OAT) did not reduce events over 7 years, there was a suggestion that the effect of treatment might differ by patient age. Baseline characteristics and outcomes by treatment with percutaneous coronary intervention (PCI) versus optimal medical therapy alone were compared by prespecified stratification at age 65 years. A p value0.01 was prespecified as significant for OAT secondary analyses. The primary outcome was death, myocardial infarction, or New York Heart Association class IV heart failure. Patients aged65 years (n = 641) were more likely to be female, to be nonsmokers, and to have hypertension, lower estimated glomerular filtration rates, and multivessel disease compared to younger patients (aged ≤65 years, n = 1,560) (p0.001). There was no significant observed interaction between treatment assignment and age for the primary outcome after adjustment (p = 0.10), and there was no difference between PCI and optimal medical therapy observed in either age group. At 7-year follow-up, younger patients tended to have angina more often compared to the older group (hazard ratio 1.21, 99% confidence interval 1.00 to 1.46, p = 0.01). The 7-year composite primary outcome was more common in older patients (p0.001), and age remained significant after covariate adjustment (hazard ratio 1.42, 99% confidence interval 1.09 to 1.84). The rate of early PCI complications was low in the 2 age groups. The trend toward a differential effect of PCI in the young versus the old for the primary outcome was likely driven by measured and unmeasured confounders and by chance. PCI reduces angina to a similar degree in the young and old. In conclusion, there is no indication for routine PCI to open a persistently occluded infarct-related artery in stable patients after myocardial infarction, regardless of age.

We propose a branch-and-cut algorithm for the VRPSPD where the constraints that ensure that the capacities are not exceeded in the middle of a route are applied in a lazy fashion. The algorithm was tested in 87 instances with 50–200 customers, finding improved lower bounds and several new optimal solutions.

This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time. We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P||∑w j T j problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||∑w j T j have been solved to optimality.

Petrobras produces nearly 90 percent of Brazil's oil at about 80 offshore oil platforms. It transports approximately 1,900 employees daily between these platforms and four mainland bases, using more than 40 helicopters that vary in capacity, operating costs, and performance characteristics. Each day, flight planners must select the helicopter routes and schedules that satisfy passenger demands. We developed a system that requires less than one hour to generate optimized flight plans that meet operational guidelines, improve travel safety, and minimize operating costs. By using this system, Petrobras reduced its number of offshore landings by 18 percent, total flight time by 8 percent, and flight costs by 14 percent, resulting in annual savings of more than $20 million. Our optimization model is a large-scale mixed integer program that generalizes prior helicopter routing models. We designed a column-generation algorithm that exploits the problem structure to overcome its computational difficulties. As part of the solution method, we use a network flow model to optimally assign passengers to selected routes.

A Content Distribution Network (CDN) is an overlay network where servers replicate contents and distribute client's requests with the aim at reducing delay, server load and network congestion, hence improving the quality of service (QoS) perceived by end clients. Because of server constraints and costs involved in the replication process, it is not reasonable to replicate the contents over the entire set of servers. In this work, exact and heuristic approaches are proposed to solve a dynamic and online problem that appears in CDN management, called the Replica Placement and Request Distribution Problem. The overall objective is to find the best servers to keep the replicas and to handle requests so that the traffic cost in the network is minimized without violating server and QoS constraints.

This paper presents an algorithm to obtain lower bounds for the Split Delivery Vehicle Routing Problem. An extended formulation over a large set of variables is provided and valid inequalities are identified. The algorithm combined column and cut generation and improved the best known lower bounds for all instances from the literature. Some reasonably sized instances are solved to optimality for the first time.

The essay discusses alternative rules for the classification of the teams in the Brazilian Soccer Championship. Three explanatory variables for the final classification are explored: the total number of goals scored and taken by each team and the results of their matches against each opponent. Two teams are placed in different classes only if their relative ranks according to a combination of these three criteria do not contradict the official ranks. The essay studies the rules for building the joint classification based on the probabilities of dominance according to these three criteria. Finally, it presents the results of the application of different rules to the data of 2006 and 2007.

This work presents an integer programming formulation for a variant of the Class-Teacher Timetabling problem, which considers the satisfaction of teacher preferences and also the proper distribution of lessons throughout the week. The formulation contains a very large number of variables and is enhanced by cuts. Therefore, a cut and column generation algorithm to solve its linear relaxation is provided. The lower bounds obtained are very good, allowing us to prove the optimality of previously known solutions in three formerly open instances.

The Hop-constrained Steiner Tree Problem is often used to model applications of multicast routing with QoS requirements. This paper introduces a distributed heuristic for the problem based on the application of dual ascent over a graph transformation introduced by Gouveia et al. The proposed algorithm is shown to yield significantly better solutions than the previously known algorithms.

OBJECTIVE To evaluate the prevalence of asymptomatic transitory myocardial ischemia during scintigraphy among amputees of vascular etiology as well as to ascertain correlation with atherothrombotic events during long-term follow-up. DESIGN A cohort, mean follow-up of 2.1 yrs study was performed in an outpatient rehabilitation clinic with 58 lower limb vascular amputees who were referred for rehabilitation, asymptomatic for coronary heart disease. Patients were evaluated for myocardial ischemia by dipyridamole scintigraphy, and occurrence of severe cardiovascular events (death, acute myocardial infarction, stroke, and peripheral ischemia with hospitalization) was assessed. RESULTS Of the 58 patients, 26 (44.8%) had positive dipyridamole myocardial scintigraphy for transitory myocardial ischemia. During follow-up, 12 subjects (20.7%), mainly diabetic patients (83%), registered a serious cardiovascular event, with 9 of 12 events having occurred in those who had tested positive for transitory ischemia on scintigraphy (P < 0.025). There were five deaths (19.2%) in those with a positive scintigraphy and a single death (3.1%) in those with a negative dipyridamole test, although the Kaplan-Meier survival curve and Cox regression were not significant (P = 0.09 and 0.1, respectively). CONCLUSIONS We found that 44.8% of patients with vascular lower limb amputation, asymptomatic for coronary disease, tested positive on myocardial scintigraphy for transitory myocardial ischemia. In a mean follow-up of 2.1 yrs, there was 10.3% of atherothrombotic events/year, with a higher death toll in those patients with positive scintigraphy.