Application-oriented Mixed Integer Non-Linear Programming

In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems. It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve. The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software). We present the main characteristics of solvers for each special case of MINLP.

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.

Mixed Mode Fracture Behaviour of Piezoelectric Materials

Piezoelectrics present an interactive electromechanical behaviour that, especially in recent years, has generated much interest since it renders these materials adapt for use in a variety of electronic and industrial applications like sensors, actuators, transducers, smart structures. Both mechanical and electric loads are generally applied on these devices and can cause high concentrations of stress, particularly in proximity of defects or inhomogeneities, such as flaws, cavities or included particles. A thorough understanding of their fracture behaviour is crucial in order to improve their performances and avoid unexpected failures. Therefore, a considerable number of research works have addressed this topic in the last decades. Most of the theoretical studies on this subject find their analytical background in the complex variable formulation of plane anisotropic elasticity. This theoretical approach bases its main origins in the pioneering works of Muskelishvili and Lekhnitskii who obtained the solution of the elastic problem in terms of independent analytic functions of complex variables. In the present work, the expressions of stresses and elastic and electric displacements are obtained as functions of complex potentials through an analytical formulation which is the application to the piezoelectric static case of an approach introduced for orthotropic materials to solve elastodynamics problems. This method can be considered an alternative to other formalisms currently used, like the Stroh’s formalism. The equilibrium equations are reduced to a first order system involving a six-dimensional vector field. After that, a similarity transformation is induced to reach three independent Cauchy-Riemann systems, so justifying the introduction of the complex variable notation. Closed form expressions of near tip stress and displacement fields are therefore obtained. In the theoretical study of cracked piezoelectric bodies, the issue of assigning consistent electric boundary conditions on the crack faces is of central importance and has been addressed by many researchers. Three different boundary conditions are commonly accepted in literature: the permeable, the impermeable and the semipermeable (“exact”) crack model. This thesis takes into considerations all the three models, comparing the results obtained and analysing the effects of the boundary condition choice on the solution. The influence of load biaxiality and of the application of a remote electric field has been studied, pointing out that both can affect to a various extent the stress fields and the angle of initial crack extension, especially when non-singular terms are retained in the expressions of the electro-elastic solution. Furthermore, two different fracture criteria are applied to the piezoelectric case, and their outcomes are compared and discussed. The work is organized as follows: Chapter 1 briefly introduces the fundamental concepts of Fracture Mechanics. Chapter 2 describes plane elasticity formalisms for an anisotropic continuum (Eshelby-Read-Shockley and Stroh) and introduces for the simplified orthotropic case the alternative formalism we want to propose. Chapter 3 outlines the Linear Theory of Piezoelectricity, its basic relations and electro-elastic equations. Chapter 4 introduces the proposed method for obtaining the expressions of stresses and elastic and electric displacements, given as functions of complex potentials. The solution is obtained in close form and non-singular terms are retained as well. Chapter 5 presents several numerical applications aimed at estimating the effect of load biaxiality, electric field, considered permittivity of the crack. Through the application of fracture criteria the influence of the above listed conditions on the response of the system and in particular on the direction of crack branching is thoroughly discussed.

Anatomic study of the feline bronchial and vascular structures with a 64 detector-row computed tomography

Multidetector row computed tomography over the last decade is commonly used in veterinary medicine. This new technology has an increased spatial and temporal resolution, could evaluate wider scanning range in shorter scanning time, providing an advanced imaging modality. Computed tomography angiographic studies are commonly used in veterinary medicine in order to evaluate vascular structures of the abdomen and the thorax. Pulmonary pathology in feline patients is a very common condition and usually is further evaluating with computed tomography. Up to date few references of the normal computed tomographic aspects of the feline thorax are reported. In this study a computed tomographic pulmonary angiography (CTPA) protocol is reported in normal cats and is compared with the up to date anatomical references. A CTPA protocol using a 64 MDCT in our study achieved high resolution images of the pulmonary arteries, pulmonary veins and bronchial lumen till the level of minor segmental branches. Feline pulmonary bronchial parenchyma demonstrates an architecture of mixed type with a monopedial model observed in the most anatomical parts and the dichotomic aspect is seen at the accessory lobe. The arterial and venous architecture is similar to the bronchial. Statistical analysis demonstrates the linear correlation of tracheal diameter to the felines weight. Vascular variations were noticed. The pulmonary venous system enters into the left atrium through three ostia (left cranial ostia: consisted of the anastomosis of the cranial and caudal portion of the left cranial pulmonary vein; right ostia: consisted of the anastomosis of the right cranial and middle pulmonary vein; and the caudal ostia: consisted of the anastomosis of the right and left caudal pulmonary vein). In conclusion CTPA is applicable in feline patients and provides an excellent imaging of the pulmonary arterial, venous and bronchial system till the level of minor segmental branches.

Fracture Mechanics Investigation of Structures with Defects

Fracture mechanics plays an important role in the material science, structure design and industrial production due to the failure of materials and structures are paid high attention in human activities. This dissertation, concentrates on some of the fractural aspects of shaft and composite which have being increasingly used in modern structures, consists four chapters within two parts. Chapters 1 to 4 are included in part 1. In the first chapter, the basic knowledge about the stress and displacement fields in the vicinity of a crack tip is introduced. A review involves the general methods of calculating stress intensity factors are presented. In Chapter 2, two simple engineering methods for a fast and close approximation of stress intensity factors of cracked or notched beams under tension, bending moment, shear force, as well as torque are presented. New formulae for calculating the stress intensity factors are proposed. One of the methods named Section Method is improved and applied to the three dimensional analysis of cracked circular section for calculating stress intensity factors. The comparisons between the present results and the solutions calculated by ABAQUS for single mode and mixed mode are studied. In chapter 3, fracture criteria for a crack subjected to mixed mode loading of two-dimension and three-dimension are reviewed. The crack extension angle for single mode and mixed mode, and the critical loading domain obtained by SEDF and MTS are compared. The effects of the crack depth and the applied force ratio on the crack propagation angle and the critical loading are investigated. Three different methods calculating the crack initiation angle for three-dimension analysis of various crack depth and crack position are compared. It should be noted that the stress intensity factors used in the criteria are calculated in section 2.1.

I tre libri di salmi vespertini a otto voci (opp. I, VII e XI) di Giovanni Paolo Colonna

Le tre raccolte di salmi da vespro a otto voci nello stile pieno di Giovanni Paolo Colonna (Bologna 1637-1695), pubblicate rispettivamente nel 1681, nel 1686 e nel 1694 (opp.I, VII e XI), costituiscono un oggetto di studio privilegiato nell’ambito della ricca produzione a stampa dell’autore: in primo luogo, esse ebbero ampia e favorevole recezione, come testimoniano la diffusione degli esemplari, le ristampe, le copie manoscritte ricavate dalle edizioni; in secondo luogo, la fortuna postuma del compositore fu legata in buona parte alla sua musica sacra a doppio coro e, in particolare, al favore riscosso dai suoi libri di salmi; infine, l’analisi delle tre raccolte consente di confrontare le risorse tecniche e stilistiche messe in opera da Colonna in composizioni afferenti a uno stesso genere ma risalenti a periodi diversi. La dissertazione è articolata in tre parti: nella prima sono presi in esame gli ordinamenti liturgici secenteschi relativi alla celebrazione dei vespri, onde illustrare la cornice rituale alla quale i salmi di Colonna erano destinati, e si passano in rassegna alcune definizioni di stile pieno e di contrappunto a otto voci desunte dalla trattatistica coeva. La seconda parte è dedicata alla lettura storico-critica delle opp. I, VII e XI nel contesto generale della produzione dell’autore. La terza parte contiene l’edizione integrale dell’opera VII e XI, nonché una scelta di brani tratti dall’op. I.