Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Lanthanide-organic frameworks for optical and catalytic applications

Este projecto de doutoramento tem como objetivo isolar e caracterizar sistematicamente novos polímeros de coordenação, no estado sólido. A presença de grupos rígidos possuindo, em particular, átomos de oxigénio e de azoto, deverá induzir interessantes propriedades fotoluminescentes (rendimentos quânticos e tempos de vida elevados, assim como vias de transferência de energia eficientes), que poderão permitir a utilização dos compostos poliméricos na produção de dispositivos funcionais. As diferentes abordagens sintéticas foram ajustadas para cada material e basearam-se, preferencialmente, nas sínteses hidrotérmicas e nas assistidas por radiação de microondas. A estrutura dos materiais foi elucidada a partir de métodos de difracção de raios X (de cristal único ou de pós) em conjunto com outras técnicas, tais como RMN de estado sólido, microscopia eletrónica, análises térmicas, espectroscopia vibracional e estudos de composição elementar. Os compostos microcristalinos foram sistematicamente estudados a fim de investigar outras propriedades além das de fotoluminescência. Alguns dos materiais revelaram multifuncionalidade apresentando simultaneamente tempos de vida na ordem dos milisegundos, elevados rendimentos quânticos e elevado desempenho como catalisadores heterogéneos. As propriedades magnéticas de um composto baseado em érbio foram igualmente estudadas, assim como as de adsorpção e permuta de solvente de uma estrutura porosa baseada em cério.

Metal-organic frameworks based on phosphonate linkers

During the last few decades, Metal-Organic Frameworks (MOFs), also known as Coordination Polymers, have attracted worldwide research attentions due to their incremented fascinating architectures and unique properties. These multidimensional materials have been potential applications in distinct areas: gas storage and separation, ion exchange, catalysis, magnetism, in optical sensors, among several others. The MOF research group at the University of Aveiro has prepared MOFs from the combination of phosphonate organic primary building units (PBUs) with, mainly, lanthanides. This thesis documents the last findings in this area involving the synthesis of multidimensional MOFs based on four di- or tripodal phosphonates ligands. The organic PBUs were designed and prepared by selecting and optimizing the best reaction conditions and synthetic routes. The self-assembly between phosphonate PBUs and rare-earths cations led to the formation of several 1D, 2D and 3D families of isotypical MOFs. The preparation of these materials was achieved by using distinct synthetic approaches: hydro(solvo)thermal, microwave- and ultrasound-assisted, one-pot and ionothermal synthesis. The selection of the organic PBUs showed to have an important role in the final architectures: while flexible phosphonate ligands afforded 1D, 2D and dense 3D structures, a large and rigid organic PBU isolated a porous 3D MOF. The crystal structure of these materials was successfully unveiled by powder or single-crystal X-ray diffraction. All multidimensional MOFs were characterized by standard solid-state techniques (FT-IR, electron microscopy (SEM and EDS), solid-state NMR, elemental and thermogravimetric analysis). Some MOF materials exhibited remarkable thermal stability and robustness up to ca. 400 ºC. The intrinsic properties of some MOFs were investigated. Photoluminescence studies revealed that the selected organic PBUs are suitable sensitizers of Tb3+ leading to the isolation of intense green-emitting materials. The suppression of the O−H quenchers by deuteration or dehydration processes improves substantially the photoluminescence of the optically-active Eu3+-based materials. Some MOF materials exhibited high heterogeneous catalytic activity and excellent regioselectivity in the ring-opening reaction of styrene oxide (PhEtO) with methanol (100% conversion of PhEtO at 55 ºC for 30 min). The porous MOF material was employed in gas separation processes. This compound showed the ability to separate propane over propylene. The ionexchanged form of this material (containing K+ cations into its network) exhibited higher affinity for CO2 being capable to separate acetylene over this environment non-friendly gas.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

Post-synthetic modification of metal–organic frameworks

Post-synthetic modification (PSM) of metal-organic frameworks encompassing the chemical transformation of the linker present is a promising new route for engineering optical centres and tuning the light emission properties of materials, both in the visible and in the near infrared (NIR) spectral regions. Here, PSM of isoreticular metal-organic framework-3 (IRMOF-3) with ethyl oxalyl monochloride, ethyl acetoacetate, pentane-2,4-dione, 3-(2- hydroxyphenyl)-3-oxopropanal, 2-chloroacetic acid, glyoxylic acid, methyl vinyl ketone and diethyl (ethoxymethylene)malonate followed by chelation of trivalent lanthanide ions afforded intriguing near infrared (Nd3+) and visible (Eu3+, Tb3+) light emitters. IRMOF-3 was used as a case in point due to both its highly porous crystalline structure and the presence of non-coordinating amino groups on the benzenedicarboxylate (bdc) linker amenable to modification. The materials were characterised by elemental analysis, powder X-ray diffraction, optical, scanning and transmission electron microscopy, Fourier transform infrared spectroscopy, and liquid and solid-state nuclear magnetic resonance. The solid-state luminescence properties of Ln-modified-IRMOF-3 were investigated at room temperature. The presence of the bdc aromatic ring, β– diketonate and oxalate enhanced the Ln3+ sensitization via ligand-to-metal energy transfer (anthena effect). As far as photocalysis is concerned, we have synthesized metal−organic frameworks (Cr-MIL-125-AC, Ag-MIL-125-AC) by a green method (solid–vapors reactions). The resulting functionalized materials show a photocatalytic activity for methylene blue degradation up to 6.52 times larger than that of the commercial photocatalyst hombikat UV-100. These findings open the door for further research for improving the photocatalytic performance of metal-organic frameworks.