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.

Free energy approximations in simple lattice proteins

This work addresses the question of whether it is possible to define simple pairwise interaction terms to approximate free energies of proteins or polymers. Rather than ask how reliable a potential of mean force is, one can ask how reliable it could possibly be. In a two-dimensional, infinite lattice model system one can calculate exact free energies by exhaustive enumeration. A series of approximations were fitted to exact results to assess the feasibility and utility of pairwise free energy terms. Approximating the true free energy with pairwise interactions gives a poor fit with little transferability between systems of different size. Adding extra artificial terms to the approximation yields better fits, but does not improve the ability to generalize from one system size to another. Furthermore, one cannot distinguish folding from nonfolding sequences via the approximated free energies. Most usefully, the methodology shows how one can assess the utility of various terms in lattice protein/polymer models. (C) 2001 American Institute of Physics.

Study of surface free energy on a lattice-gas model applied to Liquid bridge

The pulmonary crackling and the formation of liquid bridges are problems that for centuries have been attracting the attention of scientists. In order to study these phenomena, it was developed a canonical cubic lattice-gas­ like model to explain the rupture of liquid bridges in lung airways [A. Alencar et al., 2006, PRE]. Here, we further develop this model and add entropy analysis to study thermodynamic properties, such as free energy and force. The simulations were performed using the Monte Carlo method with Metropolis algorithm. The exchange between gas and liquid particles were performed randomly according to the Kawasaki dynamics and weighted by the Boltzmann factor. Each particle, which can be solid (s), liquid (l) or gas (g), has 26 neighbors: 6 + 12 + 8, with distances 1, √2 and √3, respectively. The energy of a lattice's site m is calculated by the following expression: Em = ∑k=126 Ji(m)j(k) in witch (i, j) = g, l or s. Specifically, it was studied the surface free energy of the liquid bridge, trapped between two planes, when its height is changed. For that, was considered two methods. First, just the internal energy was calculated. Then was considered the entropy. It was fond no difference in the surface free energy between this two methods. We calculate the liquid bridge force between the two planes using the numerical surface free energy. This force is strong for small height, and decreases as the distance between the two planes, height, is increased. The liquid-gas system was also characterized studying the variation of internal energy and heat capacity with the temperature. For that, was performed simulation with the same proportion of liquid and gas particle, but different lattice size. The scale of the liquid-gas system was also studied, for low temperature, using different values to the interaction Jij.

Optimization of a label-free biosensor vertically characterized based on a periodic lattice of high aspect ratio SU-8 nano-pillars with a simplified 2D theoretical model

We have recently demonstrated a biosensor based on a lattice of SU8 pillars on a 1 μm SiO2/Si wafer by measuring vertically reflectivity as a function of wavelength. The biodetection has been proven with the combination of Bovine Serum Albumin (BSA) protein and its antibody (antiBSA). A BSA layer is attached to the pillars; the biorecognition of antiBSA involves a shift in the reflectivity curve, related with the concentration of antiBSA. A detection limit in the order of 2 ng/ml is achieved for a rhombic lattice of pillars with a lattice parameter (a) of 800 nm, a height (h) of 420 nm and a diameter(d) of 200 nm. These results correlate with calculations using 3D-finite difference time domain method. A 2D simplified model is proposed, consisting of a multilayer model where the pillars are turned into a 420 nm layer with an effective refractive index obtained by using Beam Propagation Method (BPM) algorithm. Results provided by this model are in good correlation with experimental data, reaching a reduction in time from one day to 15 minutes, giving a fast but accurate tool to optimize the design and maximizing sensitivity, and allows analyzing the influence of different variables (diameter, height and lattice parameter). Sensitivity is obtained for a variety of configurations, reaching a limit of detection under 1 ng/ml. Optimum design is not only chosen because of its sensitivity but also its feasibility, both from fabrication (limited by aspect ratio and proximity of the pillars) and fluidic point of view. (© 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

Development of a Coupling Model for Fluid-Structure Interaction using the Mesh-free Finite Element Method and the Lattice Boltzmann Method

In the presented thesis work, the meshfree method with distance fields was coupled with the lattice Boltzmann method to obtain solutions of fluid-structure interaction problems. The thesis work involved development and implementation of numerical algorithms, data structure, and software. Numerical and computational properties of the coupling algorithm combining the meshfree method with distance fields and the lattice Boltzmann method were investigated. Convergence and accuracy of the methodology was validated by analytical solutions. The research was focused on fluid-structure interaction solutions in complex, mesh-resistant domains as both the lattice Boltzmann method and the meshfree method with distance fields are particularly adept in these situations. Furthermore, the fluid solution provided by the lattice Boltzmann method is massively scalable, allowing extensive use of cutting edge parallel computing resources to accelerate this phase of the solution process. The meshfree method with distance fields allows for exact satisfaction of boundary conditions making it possible to exactly capture the effects of the fluid field on the solid structure.

Phase diagram of a model for a binary mixture of nematic molecules on a Bethe lattice

We investigate the phase diagram of a discrete version of the Maier-Saupe model with the inclusion of additional degrees of freedom to mimic a distribution of rodlike and disklike molecules. Solutions of this problem on a Bethe lattice come from the analysis of the fixed points of a set of nonlinear recursion relations. Besides the fixed points associated with isotropic and uniaxial nematic structures, there is also a fixed point associated with a biaxial nematic structure. Due to the existence of large overlaps of the stability regions, we resorted to a scheme to calculate the free energy of these structures deep in the interior of a large Cayley tree. Both thermodynamic and dynamic-stability analyses rule out the presence of a biaxial phase, in qualitative agreement with previous mean-field results.

Multiphase flow in the vascular system of wood: From microscopic exploration to 3-D Lattice Boltzmann experiments

This paper provides insights into liquid free water dynamics in wood vessels based on Lattice Boltzmann experiments. The anatomy of real wood samples was reconstructed from systematic 3-D analyses of the vessel contours derived from successive microscopic images. This virtual vascular system was then used to supply fluid-solid boundary conditions to a two-phase Lattice Boltzmann scheme and investigate capillary invasion of this hydrophilic porous medium. Behavior of the liquid phase was strongly dependent on anatomical features, especially vessel bifurcations and reconnections. Various parameters were examined in numerical experiments with ideal vessel bifurcations, to clarify our interpretation of these features. (c) 2010 Elsevier Ltd. All rights reserved.

Modeling of phase equilibrium and vapor adsorption on carbon black based on a combination of a lattice theory and equation of state

A thermodynamic approach is developed in this paper to describe the behavior of a subcritical fluid in the neighborhood of vapor-liquid interface and close to a graphite surface. The fluid is modeled as a system of parallel molecular layers. The Helmholtz free energy of the fluid is expressed as the sum of the intrinsic Helmholtz free energies of separate layers and the potential energy of their mutual interactions calculated by the 10-4 potential. This Helmholtz free energy is described by an equation of state (such as the Bender or Peng-Robinson equation), which allows us a convenient means to obtain the intrinsic Helmholtz free energy of each molecular layer as a function of its two-dimensional density. All molecular layers of the bulk fluid are in mechanical equilibrium corresponding to the minimum of the total potential energy. In the case of adsorption the external potential exerted by the graphite layers is added to the free energy. The state of the interface zone between the liquid and the vapor phases or the state of the adsorbed phase is determined by the minimum of the grand potential. In the case of phase equilibrium the approach leads to the distribution of density and pressure over the transition zone. The interrelation between the collision diameter and the potential well depth was determined by the surface tension. It was shown that the distance between neighboring molecular layers substantially changes in the vapor-liquid transition zone and in the adsorbed phase with loading. The approach is considered in this paper for the case of adsorption of argon and nitrogen on carbon black. In both cases an excellent agreement with the experimental data was achieved without additional assumptions and fitting parameters, except for the fluid-solid potential well depth. The approach has far-reaching consequences and can be readily extended to the model of adsorption in slit pores of carbonaceous materials and to the analysis of multicomponent adsorption systems. (C) 2002 Elsevier Science (USA).

An anharmonic contribution to the Helmholtz free energy O(lambda 6)

The anharmonic contributions of order A6 to the Helmholtz free energy for a crystal in which every atom is on a site of inversion symmetry, have been evaluated The cor~esponding diagrams in the various orders of the perturbation theory have been presented The validity of the expressions given is for high temperatures. Numerical calculations for the diagrams which contribute to the free energy have been worked out for a nearest-n~ighbour central-force model of a facecentered cubic lattice in the high-temperature limit and in the leading term and the Ludwig approximations. The accuracy of the Ludwig approximation in evaluating the Brillouin-zone sums has been investigated. Expansion for all diagrams in the high-temperature limit has been carried out The contribution to the specific heat involves a linear as well as cubic term~ We have applied Lennard-Jones, Morse and Exponential 6 types of potentials. A comparison between the contribution to the free energy of order A6 to that of order A4 has been made.

Computing Generators of Free Modules over Orders in Group Algebras

Let E be a number field and G be a finite group. Let A be any O_E-order of full rank in the group algebra E[G] and X be a (left) A-lattice. We give a necessary and sufficient condition for X to be free of given rank d over A. In the case that the Wedderburn decomposition E[G] \cong \oplus_xM_x is explicitly computable and each M_x is in fact a matrix ring over a field, this leads to an algorithm that either gives elements \alpha_1,...,\alpha_d \in X such that X = A\alpha_1 \oplus ... \oplusA\alpha_d or determines that no such elements exist. Let L/K be a finite Galois extension of number fields with Galois group G such that E is a subfield of K and put d = [K : E]. The algorithm can be applied to certain Galois modules that arise naturally in this situation. For example, one can take X to be O_L, the ring of algebraic integers of L, and A to be the associated order A(E[G];O_L) \subseteq E[G]. The application of the algorithm to this special situation is implemented in Magma under certain extra hypotheses when K = E = \IQ.

LDA or GGA? A combined experimental inelastic neutron scattering and ab initio lattice dynamics study of alkali metal hydrides

In a previous work, we carried out inelastic neutron scattering (INS) spectroscopy experiments and preliminary first principles calculations on alkali metal hydrides. The complete series of alkali metal hydrides, LiH, NaH, KH, RbH and CsH was measured in the high-resolution TOSCA INS spectrometer at ISIS. Here, we present the results of ab initio electronic structure calculations of the properties of the alkali metal hydrides using both the local density approximation (LDA) and the generalized gradient approximation (GGA), using the Perdew–Burke–Ernzerhof (PBE) parameterization. Properties calculated were lattice parameters, bulk moduli, dielectric constants, effective charges, electronic densities and inelastic neutron scattering (INS) spectra. We took advantage of the currently available computer power to use full lattice dynamics theory to calculate thermodynamic properties for these materials. For the alkali metal hydrides (LiH, NaH, KH, RbH and CsH) using lattice dynamics, we found that the INS spectra calculated using LDA agreed better with the experimental data than the spectra calculated using GGA. Both zero-point effects and thermal contributions to free energies had an important effect on INS and several thermodynamic properties.

Solution-free sets for sums of binary forms

In this paper, we obtain quantitative estimates for the asymptotic density of subsets of the integer lattice Z2 that contain only trivial solutions to an additive equation involving binary forms. In the process we develop an analogue of Vinogradov’s mean value theorem applicable to binary forms.

Liquid crystalline cellulosic elastomers: free standing anisotropic films under stretching

The structure and local ordering of 1,6-hexamethylenediisocyanate-(acetoxypropy1) cellulose (HDI-APC) liquid crystalline elastomer thin films are investigated by using X-ray diffraction and scattering techniques. Optical microscopy and mechanical essays are performed to complement the investigation. The study is performed in films subjected or not to an uniaxial stress. Our results indicate that the film is constituted by a bundle of helicoidal fiber-like structure, where the cellobiose block spins around the axis of the fiber, like a string-structure in a smectic-like packing, with the pitch defined by a smectic-like layer. The fibers are in average perpendicular to the smectic-like planes. Without the stretch, these bundles are warped, only with a residual orientation along the casting direction. The stretch orients the bundles along it, increasing the smectic-like and the nematic-like ordering of the fibers. Under stress, the network of molecules which connects the cellobiose blocs and forms the cellulosic matrix tends to organize their links in a hexagonal-like structure with lattice parameter commensurate to the smectic-like structure.

Loss of superfluidity in a Bose-Einstein condensate on an optical lattice via a novel classical phase transition

We predict the loss of superfluidity in a Bose-Einstein condensate (BEC) trapped in a combined optical and axially-symmetric harmonic potentials during a resonant collective excitation initiated by a periodic modulation of the atomic scattering length a, when the modulation frequency equals twice the radial trapping frequency or multiples thereof. This classical dynamical transition is marked by a loss of superfluidity in the BEC and a subsequent destruction of the interference pattern upon free expansion. Suggestion for future experiment is made. (C) 2003 Elsevier B.V. B.V. All rights reserved.

Free expansion of fermionic dark solitons in a boson-fermion mixture

We use a time-dependent dynamical mean-field-hydrodynamic model to study the formation of fermionic dark solitons in a trapped degenerate Fermi gas mixed with a Bose-Einstein condensate in a harmonic as well as a periodic optical-lattice potential. The dark soliton with a 'notch' in the probability density with a zero at the minimum is simulated numerically as a nonlinear continuation of the first vibrational excitation of the linear mean-field-hydrodynamic equations, as suggested recently for pure bosons. We study the free expansion of these dark solitons as well as the consequent increase in the size of their central notch and discuss the possibility of experimental observation of the notch after free expansion.