Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Radiochemical aspects of production and processing of radiometals for preparation of metalloradiopharmaceuticals

Radiometals play an important role in nuclear medicine as involved in diagnostic or therapeutic agents. In the present work the radiochemical aspects of production and processing of very promising radiometals of the third group of the periodic table, namely radiogallium and radiolanthanides are investigated. The 68Ge/68Ga generator (68Ge, T½ = 270.8 d) provides a cyclotron-independent source of positron-emitting 68Ga (T½ = 68 min), which can be used for coordinative labelling. However, for labelling of biomolecules via bifunctional chelators, particularly if legal aspects of production of radiopharmaceuticals are considered, 68Ga(III) as eluted initially needs to be pre-concentrated and purified. The first experimental chapter describes a system for simple and efficient handling of the 68Ge/68Ga generator eluates with a cation-exchange micro-chromatography column as the main component. Chemical purification and volume concentration of 68Ga(III) are carried out in hydrochloric acid – acetone media. Finally, generator produced 68Ga(III) is obtained with an excellent radiochemical and chemical purity in a minimised volume in a form applicable directly for the synthesis of 68Ga-labelled radiopharmaceuticals. For labelling with 68Ga(III), somatostatin analogue DOTA-octreotides (DOTATOC, DOTANOC) are used. 68Ga-DOTATOC and 68Ga-DOTANOC were successfully used to diagnose human somatostatin receptor-expressing tumours with PET/CT. Additionally, the proposed method was adapted for purification and medical utilisation of the cyclotron produced SPECT gallium radionuclide 67Ga(III). Second experimental chapter discusses a diagnostic radiolanthanide 140Nd, produced by irradiation of macro amounts of natural CeO2 and Pr2O3 in natCe(3He,xn)140Nd and 141Pr(p,2n)140Nd nuclear reactions, respectively. With this produced and processed 140Nd an efficient 140Nd/140Pr radionuclide generator system has been developed and evaluated. The principle of radiochemical separation of the mother and daughter radiolanthanides is based on physical-chemical transitions (hot-atom effects) of 140Pr following the electron capture process of 140Nd. The mother radionuclide 140Nd(III) is quantitatively absorbed on a solid phase matrix in the chemical form of 140Nd-DOTA-conjugated complexes, while daughter nuclide 140Pr is generated in an ionic species. With a very high elution yield and satisfactory chemical and radiolytical stability the system could able to provide the short-lived positron-emitting radiolanthanide 140Pr for PET investigations. In the third experimental chapter, analogously to physical-chemical transitions after the radioactive decay of 140Nd in 140Pr-DOTA, the rapture of the chemical bond between a radiolanthanide and the DOTA ligand, after the thermal neutron capture reaction (Szilard-Chalmers effect) was evaluated for production of the relevant radiolanthanides with high specific activity at TRIGA II Mainz nuclear reactor. The physical-chemical model was developed and first quantitative data are presented. As an example, 166Ho could be produced with a specific activity higher than its limiting value for TRIGA II Mainz, namely about 2 GBq/mg versus 0.9 GBq/mg. While free 166Ho(III) is produced in situ, it is not forming a 166Ho-DOTA complex and therefore can be separated from the inactive 165Ho-DOTA material. The analysis of the experimental data shows that radionuclides with half-life T½ < 64 h can be produced on TRIGA II Mainz nuclear reactor, with specific activity higher than any available at irradiation of simple targets e.g. oxides.