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.

Neuroprotective activity of guanosine in an in vitro model of Alzheimer's disease

The β-Amyloid (βA) peptide is the major component of senile plaques that are one of the hallmarks of Alzheimer’s Disease (AD). It is well recognized that Aβ exists in multiple assembly states, such as soluble oligomers or insoluble fibrils, which affect neuronal viability and may contribute to disease progression. In particular, common βA-neurotoxic mechanisms are Ca2+ dyshomeostasis, reactive oxygen species (ROS) formation, altered signaling, mitochondrial dysfunction and neuronal death such as necrosis and apoptosis. Recent study shows that the ubiquitin-proteasome pathway play a crucial role in the degradation of short-lived and regulatory proteins that are important in a variety of basic and pathological cellular processes including apoptosis. Guanosine (Guo) is a purine nucleoside present extracellularly in brain that shows a spectrum of biological activities, both under physiological and pathological conditions. Recently it has become recognized that both neurons and glia also release guanine-based purines. However, the role of Guo in AD is still not well established. In this study, we investigated the machanism basis of neuroprotective effects of GUO against Aβ peptide-induced toxicity in neuronal (SH-SY5Y), in terms of mitochondrial dysfunction and translocation of phosphatidylserine (PS), a marker of apoptosis, using MTT and Annexin-V assay, respectively. In particular, treatment of SH-SY5Y cells with GUO (12,5-75 μM) in presence of monomeric βA25-35 (neurotoxic core of Aβ), oligomeric and fibrillar βA1-42 peptides showed a strong dose-dependent inhibitory effects on βA-induced toxic events. The maximum inhibition of mitochondrial function loss and PS translocation was observed with 75 μM of Guo. Subsequently, to investigate whether neuroprotection of Guo can be ascribed to its ability to modulate proteasome activity levels, we used lactacystin, a specific inhibitor of proteasome. We found that the antiapoptotic effects of Guo were completely abolished by lactacystin. To rule out the possibility that this effects resulted from an increase in proteasome activity by Guo, the chymotrypsin-like activity was assessed employing the fluorogenic substrate Z-LLL-AMC. The treatment of SH-SY5Y with Guo (75 μM for 0-6 h) induced a strong increase, in a time-dependent manner, of proteasome activity. In parallel, no increase of ubiquitinated protein levels was observed at similar experimental conditions adopted. We then evaluated an involvement of anti and pro-apoptotic proteins such as Bcl-2, Bad and Bax by western blot analysis. Interestingly, Bax levels decreased after 2 h treatment of SH-SY5Y with Guo. Taken together, these results demonstrate that Guo neuroprotective effects against βA-induced apoptosis are mediated, at least partly, via proteasome activation. In particular, these findings suggest a novel neuroprotective pathway mediated by Guo, which involves a rapid degradation of pro-apoptotic proteins by the proteasome. In conclusion, the present data, raise the possibility that Guo could be used as an agent for the treatment of AD.

Materiali Politiofenici Otticamente Attivi

Much effort has been devoted in the recent years to the investigation of optically active polythiophenes characterized by the presence of a chiral moiety linked to the 3-position of the aromatic ring. In addition to their potential technological applications as materials for enantioselective electrodes and membranes, chiral poly(thiophene)s offer the possibility of studying the structural changes accompanying the transition from the disordered state by following the variation of their chiroptical properties by circular dichroism (CD). In solution of a good solvent, that kind of polythiophenes doesn’t display any optical activity arising from the presence of dissymmetric conformation of the backbone, as shown by circular dichroism (CD) spectra. When the macromolecules begin to aggregate, as it occurs e.g. by addition of a poor solvent, or lowering the solution temperature, or when the macromolecules are assembled in the solid state as thin films obtained by solution casting or spin coating, significant CD bands are observed in the spectral region related to the electronic absorptions of the aromatic polythiophene chromophore. These CD bands are indicative of a chiral macromolecule arrangement of one prevailing chirality. The synthesis of -substituted polythiophenes can be carried out starting from the corresponding -substituted mono- or oligomeric thiophenic monomers under regioselective or regiospecific conditions in order to minimize or avoid the formation of head-to-head dyads unfavourably affecting the presence of coplanar conformations of thiophene rings as a consequence of steric interactions between the side-chain substituents, both in solution and in the solid state. To this regard, non-symmetrically substituted monomers require therefore to perform the polymerization in the presence of highly demanding catalysts and reaction condition, whereas with symmetrically substituted oligothiophenic monomers containing the -substituents located far apart from the reacting sites, it is instead possible to obtain regioregular macromolecules by adopting more simple and economic polymerization methods, such as, e. g., the chemical oxidative polymerization with iron (III) trichloride. In order to verify how the polymer structure affects its optical activity, further poly-3-alkylthiophenes, substituted by an enantiomerically pure chiral alkyl group, namely poli[3,3”-di[2((S)-(+)-2-methylbutoxy)ethyl]-2,2’:5’,2”-terthiophene] (PDMBOETT), poli[3,3’di[2((S)-(+)-2-methylbutoxy)ethyl]-2,2’-bitiofene] (PDMBOEBT), poli[3,3””-didodecyl-4’,3”’-di(S)-(+)-2-methylbutyl-2,2’:5’,2”:5”,2”’:5”’,2””-quinquethiophene (PDDDMBQT) have been synthesized and characterized by instrumental techniques. The spectroscopic behaviour of thin films of poly(DDDMBQT) has been investigated in the solid state under different sample preparation procedures. It was also compared with the behaviour of polymers previously made. The experimental results are interpreted in terms of influence of the side-chain substituents on the extent of planarity of the polymeric chains and the formation of optically active chiral aggregates. In recent years conjugated block copolymers have received considerable attention. It is well known that conjugated block copolymers composed of two electronically different blocks can have morphologic and optical properties, that differ from those of their homopolymers. A recent study has also shown that the electronic properties and the supramolecular organization of one conjugated block can also be influenced by the other block. In order to study better this behavior, a new conjugated block copolymers, composed of a regioregular hydrophylic block and a regioregular hydrophobic block namely poli[3[2-(2-metossietossi)etossi]metiltiofene]-co- poli[3(1-octilossi)tiofene], has been synthesized and characterized.

Morphological transitions in molecular and polymeric materials: patterning, fabrication, devices

This thesis individuates and characterizes irreversible transformations occurring in specific organic and oligomeric/polymeric thin films. These transformations are dewetting in discotic liquid crystals thin films and dewetting and smoothing in oligomeric and polyemeric films. Irreversible transformations are extensively characterized by means of optical and atomic force microscopy. In the case of discotic liquid crystals films the morphological characterization is performed sinchronically with electrical measurements of current during dewetting.