Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

The application of preprocessing and cutting plane techniques for a class of production planning problems

This paper investigates properties of integer programming models for a class of production planning problems. The models are developed within a decision support system to advise a sales team of the products on which to focus their efforts in gaining new orders in the short term. The products generally require processing on several manufacturing cells and involve precedence relationships. The cells are already (partially) committed with products for stock and to satisfy existing orders and therefore only the residual capacities of each cell in each time period of the planning horizon are considered. The determination of production recommendations to the sales team that make use of residual capacities is a nontrivial optimization problem. Solving such models is computationally demanding and techniques for speeding up solution times are highly desirable. An integer programming model is developed and various preprocessing techniques are investigated and evaluated. In addition, a number of cutting plane approaches have been applied. The performance of these approaches which are both general and application specific is examined.

Medição automática do diâmetro da aorta torácica em imagens de tomografia computorizada

O calibre da artéria aorta torácica é avaliado em situações de suspeita de patologia ou em pacientes com pre-disposição para desenvolverem doenças vasculares. A medição das suas dimensões, em duas direcções diametralmente opostas e, assim, fulcral na avaliação desta estrutura. Para tal, o exame de primeira linha definido é a Angiografia por Tomografia Computorizada (Angio-TC), injectando-se um produto de contraste na veia radial que irá opacificar os vasos, permitindo a sua distinção das estruturas adjacentes. O presente trabalho, inserido na disciplina de Dissertação/ Projecto/ Estágio Profissional do Mestrado em Engenharia de Computação e Instrumentação Médica e com a cooperação da empresa Efficientia, foi sugerido pela equipa de Angio-TC do Centro Hospitalar de Vila Nova de Gaia (CHVNG) e tem por objectivo o desenvolvimento de uma aplicação para a medição e registo automático do diâmetro da aorta torácica em nove pontos anatómicos pre-definidos em imagens de Tomografia Computorizada (TC). A aplicação foi desenvolvida no ambiente integrado de processamento e análise de imagem, Fiji, sendo a metodologia composta pelas etapas de segmentação, desenho da linha central, determinação dos planos de cortes, segmentação e medição da aorta nos planos de corte. Os resultados obtidos pela metodologia proposta são concordantes com os obtidos por especialistas para o conjunto de teste utilizado neste trabalho.

Métodos híbridos de pontos interiores e de programação inteira 0-1 para problemas de custo de colheita da cana-de-açúcar e de custo de coleta e geração de energia relacionados à sua biomassa

Pós-graduação em Engenharia Elétrica - FEB

Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

MATHEMATICAL MODELS AND POLYHEDRAL STUDIES FOR INTEGRAL SHEET METAL DESIGN

We deal with the optimization of the production of branched sheet metal products. New forming techniques for sheet metal give rise to a wide variety of possible profiles and possible ways of production. In particular, we show how the problem of producing a given profile geometry can be modeled as a discrete optimization problem. We provide a theoretical analysis of the model in order to improve its solution time. In this context we give the complete convex hull description of some substructures of the underlying polyhedron. Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

On arc-routing problems

Das Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.

Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous Delivery and Pick-Up

In reverse logistics networks, products (e.g., bottles or containers) have to be transported from a depot to customer locations and, after use, from customer locations back to the depot. In order to operate economically beneficial, companies prefer a simultaneous delivery and pick-up service. The resulting Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP) is an operational problem, which has to be solved daily by many companies. We present two mixed-integer linear model formulations for the VRPSDP, namely a vehicle-flow and a commodity-flow model. In order to strengthen the models, domain-reducing preprocessing techniques, and effective cutting planes are outlined. Symmetric benchmark instances known from the literature as well as new asymmetric instances derived from real-world problems are solved to optimality using CPLEX 12.1.

Economic and Environmental Optimization of Ornamental Stone Block Cutting with a 3D Algorithm

This thesis focuses on finding the optimum block cutting dimensions in terms of the environmental and economic factors by using a 3D algorithm for a limestone quarry in Foggia, Italy. The environmental concerns of quarrying operations are mainly: energy consumption, material waste, and pollution. The main economic concerns are the block recovery, the selling prices, and the production costs. Fractures adversely affect the block recovery ratio. With a fracture model, block production can be optimized. In this research, the waste volume produced by quarrying was minimised to increase the recovery ratio and ensure economic benefits. SlabCutOpt is a software developed at DICAM–University of Bologna for block cutting optimization which tests different cutting angles on the x-y-z planes to offer up alternative cutting methods. The program tests several block sizes and outputs the optimal result for each entry. By using SlabCutOpt, ten different block dimensions were analysed, the results indicated the maximum number of non-intersecting blocks for each dimension. After analysing the outputs, the block named number 1 with the dimensions ‘1mx1mx1m’ had the highest recovery ratio as 43% and the total Relative Money Value (RMV) with a value of 22829. Dimension number 1, also had the lowest waste volume, with a value of 3953.25 m3, for the total bench. For cutting the total bench volume of 6932.25m3, the diamond wire cutter had the lowest dust emission values for the block with the dimension ‘2mx2mx2m’, with a value of 24m3. When compared with the Eco-Label standards, block dimensions having surface area values lower than 15m2, were found to fit the natural resource waste criteria of the label, as the threshold required 25% of minimum recovery [1]. Due to the relativity of production costs, together with the Eco-Label threshold, the research recommends the selection of the blocks with a surface area value between 6m2 and 14m2.

Nutritional characteristics and in vitro digestibility of silages from different corn cultivars harvested at two cutting heights

The objective of this study was to evaluate the nutritional traits and in vitro digestibility of silages from different corn cultivars harvested at two cutting heights. It was evaluated 11 cultivars (Dina 766, Dina 657, Dina 1000, P 3021, P 3041, C 805, C 333, AG 5011, FO 01, Dina co 9621 and BR 205) harvest 5 cm above ground (low) and 5 cm below the intersection of the first ear (high). It was used a random block design (three blocks), arranged in a 11 × 2 factorial scheme. Silages from plants harvested at high cutting height presented average content of dry matter significantly superior to silages from plants harvested at low height. Cultivars FO 01, AG 5011, Dina co 9621 and Dina 766 presented greater content of crude protein than cultivars C 805, P 3041 and P 3021, which presented the lowest contents of this nutrient. The raise in the cut height increased in vitro dry matter true digestibility coefficients and in vitro dry matter digestibility of silage evaluated. The increase in cut height improved nutritive value of silages by decreasing concentrations of fibrous fractions and increasing in vitro dry matter digestibility.

Evaluation of corn cultivars harvested at two cutting heights for ensilage

The objective of this study was to evaluate the agronomic characteristics, bromatological-chemical composition and digestibility of 11 corn cultivars (Zea mays) harvested at two cutting heights. Cultivars D 766, D 657, D 1000, P 3021, P 3041, C 805, C 333, AG 5011, FO 01, CO 9621 and BR 205 were evaluated when they were harvested 5 cm above ground (low) and 5 cm below the insertion of the first ear (high). The experiment was designed as random blocks, with three replicates, arranged in an 11 x 2 factorial scheme. Cultivars presented similar productions of forage dry matter and grains. Percentages of stalk, leaf, straw, cob and kernel fractions were different among cultivars, as well as dry matter content of the whole plant at harvest. Considering the whole plant, only the contents of gross energy, nitrogen in neutral detergent fiber, and in vitro neutral and acid detergent fiber digestibility did not differ among cultivars. Increase on the cutting height improved forage quality due to the reduction of stalk and leaf fractions and contents of cell wall constituents.

Herbage accumulation, growth and structural characteristics of Mombasa grass (Panicum maximum Jacq.) harvested at different cutting intervals

The objective of the present study was to evaluate herbage accumulation, morphological composition, growth rate and structural characteristics in Mombasa grass swards subject to different cutting intervals (3, 5 and 7 wk) during the rainy and dry seasons of the year. Treatments were assigned to experimental units (17.5 m(2)) according to a complete randomised block design, with four replicates. Herbage accumulation was greater in the rainy than in the dry season (83 and 17%, respectively). Herbage accumulation (24,300 kg DM ha(-1)), average growth rate (140 kg DM ha(-1) d(-1)) and sward height (111 cm) were highest in the 7 wk cutting interval, but leaf proportion (56%), leaf:stem (1.6) and leaf:non leaf (1.3) ratios decreased. Herbage accumulation, morphological composition and sward structure of Mombasa grass sward may be manipulated through defoliation frequency. The highest leaf proportion was recorded in the 3-wk cutting interval. Longer cutting intervals affected negatively sward structure, with potential negative effects on utilization efficiency, animal intake and performance.

Contribution to dynamic characteristics of the cutting temperature in the drilling process considering one dimension heat flow

The machining of hardened steels has always been a great challenge in metal cutting, particularly for drilling operations. Generally, drilling is the machining process that is most difficult to cool due to the tool`s geometry. The aim of this work is to determine the heat flux and the coefficient of convection in drilling using the inverse heat conduction method. Temperature was assessed during the drilling of hardened AISI H13 steel using the embedded thermocouple technique. Dry machining and two cooling/lubrication systems were used, and thermocouples were fixed at distances very close to the hole`s wall. Tests were replicated for each condition, and were carried out with new and worn drills. An analytical heat conduction model was used to calculate the temperature at tool-workpiece interface and to define the heat flux and the coefficient of convection. In all tests using new and worn out drills, the lowest temperatures and decrease of heat flux were observed using the flooded system, followed by the MQL, considering the dry condition as reference. The decrease of temperature was directly proportional to the amount of lubricant applied and was significant in the MQL system when compared to dry cutting. (C) 2011 Elsevier Ltd. All rights reserved.