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.

Crystal engineering of co-crystals and host-guest systems for environmentally friendly applications: sunscreens stabilization, pollutant sequestering and herbicide reformulation.

Solid state engineered materials have proven to be useful and suitable tools in the quest of new materials. In this thesis different crystalline compounds were synthesized to provide more sustainable products for different applications, as in cosmetics or in agrochemistry, to propose pollutants removal strategy or to obtain materials for electrocatalysis. Therefore, the research projects presented here can be divided into three main topics: (i) sustainable preparation of solid materials of widely used active ingredients aimed at the reduction of their occurrence in the natural environment. The systems studied in this section are cyclodextrins host-guest compounds, obtained via mechanochemical and slurry synthesis. The first chemicals studied are sunscreens inclusion complexes, that proved to have enhanced photostability and desired photoprotection. The same synthetic methods were applied to obtain inclusion complexes of bentazon, a herbicide often found to leach in groundwaters. The resulting products showed to have desired water solubility properties. The same herbicide was also adsorbed on amorphous calcium phosphate nanoparticles, to obtain a biocompatible formulation of this agrochemical. This herbicide could benefit by the adsorption on nanoparticles for what concerns its kinetic release in different media as well as its photostability. (ii) Sustainable synthesis of co-crystals based on polycyclic aromatic hydrocarbons, for the proposal of a sequestering method with a resulting material with enhanced properties. The co-crystallization via mechanochemical means proved that these pollutants can be sequestered via simple solvent-free synthesis and the obtained materials present better photochemical properties when compared to the starting co-formers. (iii) Crystallization from mild solvents of nanosized materials useful for the application in electrocatalysis. The study of compounds based on nickel and cobalt metal ions resulted in the obtainment of 2D and 1D coordination polymers. Moreover, solid solutions were obtained. These crystals showed layered structures and, according to preliminary results, they can be exfoliated.