Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Hydroelastic impacts of deformable wedges

This work investigates the slamming phenomenon experienced during the water entry of deformable bodies. Wedges are chosen as reference geometry due to their similarity to a generic hull section. Hull slamming is a phenomenon occurring when a ship re-enters the water after having been partially or completely lifted out the water. While the analysis of rigid structures entering the water has been extensively studied in the past and there are analytical solutions capable of correctly predicting the hydrodynamic pressure distribution and the overall impact dynamics, the effect of the structural deformation on the structural force is still a challenging problem to be solved. In fact, in case of water impact of deformable bodies, the dynamic deflection could interact with the fluid flow, changing the hydrodynamic load. This work investigates the hull-slamming problem by experiments and numerical simulations of the water entry of elastic wedges impacting on an initially calm surface. The effect of asymmetry due to horizontal velocity component or initial tilt angle on the impact dynamics is also studied. The objective of this work is to determine an accurate model to predict the overall dynamics of the wedge and its deformations. More than 1200 experiments were conducted by varying wedge structural stiffness, deadrise angle, impact velocity and mass. On interest are the overall impact dynamics and the local structural deformation of the panels composing the wedge. Alongside with the experimental analysis, numerical simulations based on a coupled Smoothed Particle Hydrodynamics (SPH) and FEM method are developed. The experimental results provide evidence of the mutual interaction between hydrodynamic load and structural deformation. It is found a simple criterion for the onset of fluid structure interaction (FSI), giving reliable information on the cases where FSI should been taken into account.

Fluid-structure interaction by a coupled lattice Boltzmann-finite element approach

In this thesis, a strategy to model the behavior of fluids and their interaction with deformable bodies is proposed. The fluid domain is modeled by using the lattice Boltzmann method, thus analyzing the fluid dynamics by a mesoscopic point of view. It has been proved that the solution provided by this method is equivalent to solve the Navier-Stokes equations for an incompressible flow with a second-order accuracy. Slender elastic structures idealized through beam finite elements are used. Large displacements are accounted for by using the corotational formulation. Structural dynamics is computed by using the Time Discontinuous Galerkin method. Therefore, two different solution procedures are used, one for the fluid domain and the other for the structural part, respectively. These two solvers need to communicate and to transfer each other several information, i.e. stresses, velocities, displacements. In order to guarantee a continuous, effective, and mutual exchange of information, a coupling strategy, consisting of three different algorithms, has been developed and numerically tested. In particular, the effectiveness of the three algorithms is shown in terms of interface energy artificially produced by the approximate fulfilling of compatibility and equilibrium conditions at the fluid-structure interface. The proposed coupled approach is used in order to solve different fluid-structure interaction problems, i.e. cantilever beams immersed in a viscous fluid, the impact of the hull of the ship on the marine free-surface, blood flow in a deformable vessels, and even flapping wings simulating the take-off of a butterfly. The good results achieved in each application highlight the effectiveness of the proposed methodology and of the C++ developed software to successfully approach several two-dimensional fluid-structure interaction problems.