Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.

In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.

The 0-1 Knapsack polytope – a starting point for cryptanalysis of Knapsack ciphers?

The Knapsack Cryptosystem of Merkle and Hellman, 1978, is one of the earliest public-key cryptography schemes. The security of the method relies on the difficulty in solving Subset Sum Problems (also known as Knapsack Problems). In this paper, we first provide a brief history of knapsack-based cryptosystems and their cryptanalysis attacks. Following that, we review the advances in integer programming approaches to 0 − 1 Knapsack Problems, with a focus on the polyhedral studies of the convex hull of the integer set. Last of all, we discuss potential future research directions in applying integer programming in the cryptanalysis of knapsack ciphers.

Twistor and polytope interpretations for subleading color one-loop amplitudes

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A polytope DNA vaccine elicits multiple effector and memory CTL responses and protects against human papillomavirus 16 E7-expressing tumour

Vaccine-induced CD8 T cells directed to tumourspecific antigens are recognised as important components of protective and therapeutic immunity against tumours. Where tumour antigens have pathogenic potential or where immunogenic epitopes are lost from tumours, development of subunit vaccines consisting of multiple individual epitopes is an attractive alternative to immunising with whole tumour antigen. In the present study we investigate the efficacy of two DNA-based multiepitope('polytope') vaccines containing murine (H-2(b)) and human (HLA-A* 0201)-restricted epitopes of the E7 oncoprotein of human papillomavirus type 16, in eliciting tumour-protective cytotoxic T-lymphocyte (CTL) responses. We show that the first of these polytopes elicited powerful effector CTL responses ( measured by IFN-gamma ELISpot) and long-lived memory CTL responses ( measured by functional CTL assay and tetramers) in immunised mice. The responses could be boosted by immunisation with a recombinant vaccinia virus expressing the polytope. Responses induced by immunisation with polytope DNA alone partially protected against infection with recombinant vaccinia virus expressing the polytope. Complete protection was afforded against challenge with an E7-expressing tumour, and reduced growth of nascent tumours was observed. A second polytope differing in the exact composition and order of CTL epitopes, and lacking an inserted endoplasmic reticulum targeting sequence and T-helper epitope, induced much poorer CTL responses and failed to protect against tumour challenge. These observations indicate the validity of a DNA polytope vaccine approach to human papillomavirus E7 - associated carcinoma, and underscore the importance of design in polytope vaccine construction.

The changing face and role of CACSD

Computer Aided Control Engineering involves three parallel streams: Simulation and modelling, Control system design (off-line), and Controller implementation. In industry the bottleneck problem has always been modelling, and this remains the case - that is where control (and other) engineers put most of their technical effort. Although great advances in software tools have been made, the cost of modelling remains very high - too high for some sectors. Object-oriented modelling, enabling truly re-usable models, seems to be the key enabling technology here. Software tools to support control systems design have two aspects to them: aiding and managing the work-flow in particular projects (whether of a single engineer or of a team), and provision of numerical algorithms to support control-theoretic and systems-theoretic analysis and design. The numerical problems associated with linear systems have been largely overcome, so that most problems can be tackled routinely without difficulty - though problems remain with (some) systems of extremely large dimensions. Recent emphasis on control of hybrid and/or constrained systems is leading to the emerging importance of geometric algorithms (ellipsoidal approximation, polytope projection, etc). Constantly increasing computational power is leading to renewed interest in design by optimisation, an example of which is MPC. The explosion of embedded control systems has highlighted the importance of autocode generation, directly from modelling/simulation products to target processors. This is the 'new kid on the block', and again much of the focus of commercial tools is on this part of the control engineer's job. Here the control engineer can no longer ignore computer science (at least, for the time being). © 2006 IEEE.

The changing face and role of CACSD

Computer Aided Control Engineering involves three parallel streams: Simulation and modelling, Control system design (off-line), and Controller implementation. In industry the bottleneck problem has always been modelling, and this remains the case - that is where control (and other) engineers put most of their technical effort. Although great advances in software tools have been made, the cost of modelling remains very high - too high for some sectors. Object-oriented modelling, enabling truly re-usable models, seems to be the key enabling technology here. Software tools to support control systems design have two aspects to them: aiding and managing the work-flow in particular projects (whether of a single engineer or of a team), and provision of numerical algorithms to support control-theoretic and systems-theoretic analysis and design. The numerical problems associated with linear systems have been largely overcome, so that most problems can be tackled routinely without difficulty - though problems remain with (some) systems of extremely large dimensions. Recent emphasis on control of hybrid and/or constrained systems is leading to the emerging importance of geometric algorithms (ellipsoidal approximation, polytope projection, etc). Constantly increasing computational power is leading to renewed interest in design by optimisation, an example of which is MPC. The explosion of embedded control systems has highlighted the importance of autocode generation, directly from modelling/simulation products to target processors. This is the 'new kid on the block', and again much of the focus of commercial tools is on this part of the control engineer's job. Here the control engineer can no longer ignore computer science (at least, for the time being). ©2006 IEEE.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

K-Theory of non-linear projective toric varieties

We define a category of quasi-coherent sheaves of topological spaces on projective toric varieties and prove a splitting result for its algebraic K-theory, generalising earlier results for projective spaces. The splitting is expressed in terms of the number of interior lattice points of dilations of a polytope associated to the variety. The proof uses combinatorial and geometrical results on polytopal complexes. The same methods also give an elementary explicit calculation of the cohomology groups of a projective toric variety over any commutative ring.

Politopo de Birkhoff acíclico

Neste trabalho estabelece-se uma interpreta c~ao geom etrica, em termos da teoria dos grafos, para v ertices, arestas e faces de uma qualquer dimens~ao do politopo de Birkho ac clico, Tn = n(T), onde T e uma arvore com n v ertices. Generaliza-se o resultado obtido por G. Dahl, [18], para o c alculo do di^ametro do grafo G( t n), onde t n e o politopo das matrizes tridiagonais duplamente estoc asticas. Adicionalmente, para q = 0; 1; 2; 3 s~ao obtidas f ormulas expl citas para a contagem do n umero de q faces do politopo de Birkho tridiagonal, t n, e e feito o estudo da natureza geom etrica dessas mesmas faces. S~ao, tamb em, apresentados algoritmos para efectuar contagens do n umero de faces de dimens~ao inferior a de uma dada face do politopo de Birkho ac clico.

Estimation bayésienne nonparamétrique de copules

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Brisure de symétrie par la réduction des groupes de Lie simples à leurs sous-groupes de Lie réductifs maximaux

Dans ce travail, nous exploitons des propriétés déjà connues pour les systèmes de poids des représentations afin de les définir pour les orbites des groupes de Weyl des algèbres de Lie simples, traitées individuellement, et nous étendons certaines de ces propriétés aux orbites des groupes de Coxeter non cristallographiques. D'abord, nous considérons les points d'une orbite d'un groupe de Coxeter fini G comme les sommets d'un polytope (G-polytope) centré à l'origine d'un espace euclidien réel à n dimensions. Nous introduisons les produits et les puissances symétrisées de G-polytopes et nous en décrivons la décomposition en des sommes de G-polytopes. Plusieurs invariants des G-polytopes sont présentés. Ensuite, les orbites des groupes de Weyl des algèbres de Lie simples de tous types sont réduites en l'union d'orbites des groupes de Weyl des sous-algèbres réductives maximales de l'algèbre. Nous listons les matrices qui transforment les points des orbites de l'algèbre en des points des orbites des sous-algèbres pour tous les cas n<=8 ainsi que pour plusieurs séries infinies des paires d'algèbre-sous-algèbre. De nombreux exemples de règles de branchement sont présentés. Finalement, nous fournissons une nouvelle description, uniforme et complète, des centralisateurs des sous-groupes réguliers maximaux des groupes de Lie simples de tous types et de tous rangs. Nous présentons des formules explicites pour l'action de tels centralisateurs sur les représentations irréductibles des algèbres de Lie simples et montrons qu'elles peuvent être utilisées dans le calcul des règles de branchement impliquant ces sous-algèbres.

Sur une classe de structures kählériennes généralisées toriques

Cette thèse concerne le problème de trouver une notion naturelle de «courbure scalaire» en géométrie kählérienne généralisée. L'approche utilisée consiste à calculer l'application moment pour l'action du groupe des difféomorphismes hamiltoniens sur l'espace des structures kählériennes généralisées de type symplectique. En effet, il est bien connu que l'application moment pour la restriction de cette action aux structures kählériennes s'identifie à la courbure scalaire riemannienne. On se limite à une certaine classe de structure kählériennes généralisées sur les variétés toriques notée $DGK_{\omega}^{\mathbb{T}}(M)$ que l'on reconnaît comme étant classifiées par la donnée d'une matrice antisymétrique $C$ et d'une fonction réelle strictement convexe $\tau$ (ayant un comportement adéquat au voisinage de la frontière du polytope moment). Ce point de vue rend évident le fait que toute structure kählérienne torique peut être déformée en un élément non kählérien de $DGK_{\omega}^{\mathbb{T}}(M)$, et on note que cette déformation à lieu le long d'une des classes que R. Goto a démontré comme étant libre d'obstruction. On identifie des conditions suffisantes sur une paire $(\tau,C)$ pour qu'elle donne lieu à un élément de $DGK_{\omega}^{\mathbb{T}}(M)$ et on montre qu'en dimension 4, ces conditions sont également nécessaires. Suivant l'adage «l'application moment est la courbure» mentionné ci-haut, des formules pour des notions de «courbure scalaire hermitienne généralisée» et de «courbure scalaire riemannienne généralisée» (en dimension 4) sont obtenues en termes de la fonction $\tau$. Enfin, une expression de la courbure scalaire riemannienne généralisée en termes de la structure bihermitienne sous-jacente est dégagée en dimension 4. Lorsque comparée avec le résultat des physiciens Coimbra et al., notre formule suggère un choix canonique pour le dilaton de leur théorie.

Recurrence and higher ergodic properties for quenched random Lorentz tubes in dimension bigger than two

We consider the billiard dynamics in a non-compact set of ℝ d that is constructed as a bi-infinite chain of translated copies of the same d-dimensional polytope. A random configuration of semi-dispersing scatterers is placed in each copy. The ensemble of dynamical systems thus defined, one for each global realization of the scatterers, is called quenched random Lorentz tube. Under some fairly general conditions, we prove that every system in the ensemble is hyperbolic and almost every system is recurrent, ergodic, and enjoys some higher chaotic properties.

Partial spectral projected gradient method with active-set strategy for linearly constrained optimization

A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithm. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the Tango Project web page: http://www.ime.usp.br/similar to egbirgin/tango/.

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.