Non-classical preference models in combinatorial problems: Models and algorithms for graphs

This is a summary of the most important results presented in the authors PhD thesis (Spanjaard 2003). This thesis, written in French, was defended on 16 December 2003 and supervised by Patrice Perny. A copy is available from the author upon request. This thesis deals with the search for preferred solutions in combinatorial optimization problems (and more particularly graph problems). It aims at conciliating preference modelling and algorithmic concerns for decision aiding.Received: March 2004, MSC classification: 91B06, 90C27, 90B40, 16Y60     

Railroad infrastructure operations : Modeling and resolution

This is a summary of the main results presented in the au-thors PhD thesis. This thesis was supervised by Arnaud Fréville, Xavier Gandibleux and Joaquín Rodriguez, and defended on 10 December 2003 at the University of Valenciennes (France). It is written in French and is available at http: //www3.inrets.fr/~delorme/Papiers/These/These.pdf. This work deals with a real-world planning problem in railroad infrastructure operations. It proposes a new multiobjective linear model of the problem, using an overall set packing structure, as well as several algorithms dedicated to set packing resolution. It also discusses the integration of this research in a decision support system for evaluating railroad infrastructure capacity.Received: June 2004, MSC classification: 90B06, 90C27, 90C59, 90C29     

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming

We briefly describe the contents of the authors PhD thesis (see Colson 2003) discussed on July 2003 at the University of Namur (Belgium) and supervised by Philippe L. Toint. The contributions presented in this thesis are the development of trust-region methods for solving two particular classes of mathematical programs, namely derivative-free optimization (DFO) problems and nonlinear bilevel programming problems. The thesis is written in English and is available via the author.Received: July 2003, AMS classification: 65D05, 90C30, 90C56, 90C59     

Solving scheduling problems from high-level models

This is the summary of the author??s PhD thesis supervised by Yves Deville and Pascal Van Hentenryck, and defended on 25 May 2010?at the Université catholique de Louvain in Louvain-la-Neuve. The thesis is written in English and is available from the author, or downloadable from http://becool.info.ucl.ac.be/files2/thesis-monette.pdf. This work is about the gap between high-level modelling of scheduling problems and its efficient resolution. We propose to automatically classify models of scheduling problems, and to apply an appropriate search algorithm. Thanks to the strong separation between model and search, we propose also a simple way to create hybrid algorithms. A second part of the thesis deals with Constraint Programming approaches for two scheduling problems: The one-machine non-preemptive problem and the Just-In-Time Job-Shop problem. All parts are accompanied by experimental results showing their practicality.     

Upper and lower bounds for the fixed spectrum frequency assignment problem

A survey of the results described in the authors PhD thesis (Montemanni 2001) is presented. The thesis, which was supervised by Prof. Derek H. Smith and Dr. Stuart M. Allen, has been defended in January 2002 at the University of Glamorgan (U.K.). The thesis proposes new heuristic algorithms, based on well-known meta-heuristic paradigms, and new lower bounding techniques, based on linear programming, for the fixed spectrum frequency assignment problem.Received: May 2003, Revised: May 2003, AMS classification: 90C27, 90C59,05C90, 90C05Roberto Montemanni: Present address: Istituto Dalle Molle di Studi sullIntelligenza Artificiale (IDSIA), Galleria 2, 6928 Manno-Lugano, Switzerland (e-mail: roberto@idsia.ch)     

Concentrator location in telecommunications

We survey the main results in the authors PhD Thesis presented in December 2002 at the Université Libre de Bruxelles and supervised by Prof. Martine Labbé. The dissertation is written in English and is available at smg.ulb.ac.be. Several versions of concentrator location problems in telecommunication networks are studied. The thesis presents a list of polyhedral results for these problems and a branch and cut algorithm for the most general problem introduced.Received: October 2003, AMS classification: 90B80, 90B18, 90C57     

An uncertainty principle on homogeneous trees

Let be a homogeneous tree of degree . We prove an uncertainty principle in this setting regarding ``exponentially decreasing' functions on trees whose Fourier transforms have a ``deep zero'.

     

Routing,districting and location for arc traversal problems

We summarize the main results of the authors PhD thesis, defended in February 2003 at the Katholieke Universiteit Leuven (Belgium) and supervised by Dirk Cattrysse. The thesis is written in English and presents a number of solution and modeling approaches for distribution problems in the context of arc routing. In particular, the focus is on (1) local search procedures for arc routing problems, (2) district design for arc routing applications and (3) the study of location aspects in relation with districting and arc routing.AMS classification: 90B06, 05C38, 90C35, 90C59     

A framework for robust and flexible optimisation using metaheuristics

This is a summary of the most important results presented in the authors PhD thesis. This thesis, written in English, was defended on 13 June 2003 and supervised by Johan Springael and Gerrit K. Janssens. A copy is available from the author upon request. This PhD thesis focuses on stochastic problems and develops a framework to find robust and flexible solutions of such problems. The framework is applied to several well-known problems in the realm of supply chain design. Besides this framework, the thesis contains several other important contributions. A new type of robustness and flexibility is proposed, that expresses the need for solutions to remain approximately the same when changes occur in the problem data. Several distance measures are developed to calculate the distance (or similarity) between solutions of different permutation type problems. A new type of genetic algorithm is also proposed, that uses a distance measure to maintain a diverse population of high-quality solutions.Received: June 2003     

A geometric characterization of Vassiliev invariants

It is a well-known paradigm to consider Vassiliev invariants as polynomials on the set of knots. We prove the following characterization: a rational knot invariant is a Vassiliev invariant of degree if and only if it is a polynomial of degree on every geometric sequence of knots. Here a sequence with is called geometric if the knots coincide outside a ball , inside of which they satisfy for all and some pure braid . As an application we show that the torsion in the braid group over the sphere induces torsion at the level of Vassiliev invariants: there exist knots in that can be distinguished by -invariants of finite type but not by rational invariants of finite type. In order to obtain such torsion invariants we construct over a universal Vassiliev invariant of degree for knots in .

     

The Laplacian MASA in a free group factor

The Laplacian (or radial) masa in a free group factor is generated by the sum of the generators and their inverses. We show that such a masa is strongly singular and has Popa invariant . This is achieved by proving that the conditional expectation onto is an asymptotic homomorphism. We also obtain similar results for the free product of discrete groups, each of which contains an element of infinite order.

     

Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms

We consider the multiple shift scheduling problem modelled as a covering problem. Such problems are characterized by a constraint matrix that has, in every column, blocks of consecutive 1s, each corresponding to a shift. We focus on three types of shift scheduling problems classified according to the column structure in the constraint matrix: columns of consecutive 1s, columns of cyclical 1s, and columns of k consecutive blocks. In particular, the complexity of the cyclical scheduling problem, where the matrix satisfies the property of cyclical 1s in each column, was noted recently by Hochbaum and Tucker to be open. They further showed that the unit demand case is polynomially solvable. Here we extend this result to the uniform requirements case, and provide a 2-approximation algorithm for the non-uniform case. We also establish that the cyclical scheduling problem’s complexity is equivalent to that of the exact matching problem—a problem the complexity status of which is known to be randomized polynomial (RP). We then investigate the three types of shift scheduling problems and show that, while the consecutive ones version is polynomial and the k-block columns version is NP-hard (for k≥2), for the k-blocks problem we give a simple k-approximation algorithm, which is the first approximation algorithm determined for the problem.     

Compensated compactness for nonlinear homogenization and reduction of dimension

We study the limit behaviour of some nonlinear monotone equations, such as: , in a domain which is thin in some directions (e.g. is a plate or a thin cylinder). After rescaling to a fixed domain , the above equation is transformed into: , with convenient operators and . Assuming that and the inverse of have particular forms and satisfy suitable compensated compactness assumptions, we prove a closure result, that is we prove that the limit problem has the same form. This applies in particular to the limit behaviour of nonlinear monotone equations in laminated plates.Received: 16 October 2002, Accepted: 12 June 2003, Published online: 22 September 2003Mathematics Subject Classification (2000): 35B27, 35B40, 74Q15     

Intersections of two cofinite subfields

Let F be a field finite-dimensional over subfields A and B. It is known from Galois theory that the degree can be infinite. If F is purely inseparable over B and finitely generated over the prime field, this cannot happen; but it can happen when F is not finitely generated. Received: 15 July 2003     

A note on invertibility preservers on Banach algebras

Let be be semisimple Banach algebras and let be a unital bijective linear operator that preserves invertibility. If the socle of is an essential ideal of , then is a Jordan isomorphism.

     

A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems

We improve the well-known result presented in Bertsimas and Sim (Math Program B98:49–71, 2003) regarding the computation of optimal solutions of Robust Combinatorial Optimization problems with interval uncertainty in the objective function coefficients. We also extend this improvement to a more general class of Combinatorial Optimization problems with interval uncertainty.     

A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377

The standard algorithm for testing reducibility of a trinomial of prime degree over requires bits of memory. We describe a new algorithm which requires only bits of memory and significantly fewer memory references and bit-operations than the standard algorithm.

If is a Mersenne prime, then an irreducible trinomial of degree is necessarily primitive. We give primitive trinomials for the Mersenne exponents , , and . The results for extend and correct some computations of Kumada et al. The two results for are primitive trinomials of the highest known degree.

     

Expanding maps on infra-nilmanifolds of homogeneous type

In this paper we investigate expanding maps on infra-nilmanifolds. Such manifolds are obtained as a quotient , where is a connected and simply connected nilpotent Lie group and is a torsion-free uniform discrete subgroup of , with a compact subgroup of . We show that if the Lie algebra of is homogeneous (i.e., graded and generated by elements of degree 1), then the corresponding infra-nilmanifolds admit an expanding map. This is a generalization of the result of H. Lee and K. B. Lee, who treated the 2-step nilpotent case.