Dynamic Global Constraints in Backtracking Based Environments

Global constraints provide strong filtering algorithms to reduce the search space when solving large combinatorial problems. In this paper we propose to make the global constraints dynamic, i.e., to allow extending the set of constrained variables during search. We describe a generic dynamisation technique for an arbitrary monotonic global constraint and we compare it with the semantic-based dynamisation for the alldifferent constraint. At the end we sketch a dynamisation technique for non-monotonic global constraints. A comparison with existing methods to model dynamic problems is given as well.     

On computation of the greatest common divisor of several polynomials over a finite field

We propose a probabilistic algorithm to reduce computing the greatest common divisor of m polynomials over a finite field (which requires computing m−1 pairwise greatest common divisors) to computing the greatest common divisor of two polynomials over the same field.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

A Quasi-Newton Penalty Barrier Method for Convex Minimization Problems

We describe an infeasible interior point algorithm for convex minimization problems. The method uses quasi-Newton techniques for approximating the second derivatives and providing superlinear convergence. We propose a new feasibility control of the iterates by introducing shift variables and by penalizing them in the barrier problem. We prove global convergence under standard conditions on the problem data, without any assumption on the behavior of the algorithm.     

A parallel method for time discretization of parabolic equations based on Laplace transformation and quadrature

We consider the discretization in time of an inhomogeneous parabolicequation in a Banach space setting, using a representation ofthe solution as an integral along a smooth curve in the complexleft half-plane which, after transformation to a finite interval,is then evaluated to high accuracy by a quadrature rule. Thisreduces the problem to a finite set of elliptic equations withcomplex coefficients, which may be solved in parallel. The paperis a further development of earlier work by the authors, wherewe treated the homogeneous equation in a Hilbert space framework.Special attention is given here to the treatment of the forcingterm. The method is combined with finite-element discretizationin spatial variables.     

Computing Zeta Functions of Kummer Curves via Multiplicative Characters

We present a practical polynomial-time algorithm for computing the zeta function of a Kummer curve over a finite field of small characteristic. Such algorithms have recently been obtained using a method of Kedlaya based upon Monsky–Washnitzer cohomology, and are of interest in cryptography. We take a different approach. The problem is reduced to that of computing the L-function of a multiplicative character sum. This latter task is achieved via a cohomological formula based upon the work of Dwork and Reich. We show, however, that our method and that of Kedlaya are very closely related.Dedicated to the memory of Gian-Carlo Rota     

CONVERGENCE OF CASCADE ALGORITHMS AND SMOOTHNESS OF REFINABLE DISTRIBUTIONS

In this paper, the author at first develops a method to study convergence of the cascade algorithm in a Banach space without stable assumption on the initial (see Theorem 2.1), and then applies the previous result on the convergence to characterizing compactly supported refinable distributions in fractional Sobolev spaces and Holder continuous spaces (see Theorems 3.1, 3.3, and 3.4). Finally the author applies the above characterization to choosing appropriate initial to guarantee the convergence of the cascade algorithm (see Theorem 4.2).     

Embedding optimisation algorithms with Mosel

Algebraic modelling languages allow models to be implemented in such a way that they can easily be understood and modified. They are therefore a working environment commonly used by practitioners in Operations Research. Having once developed models, they need to be integrated inside the company information system. This step often involves embedding a model into a programming language environment: many existing algebraic modelling languages make possible to run parameterised models and subsequently retrieve their results, but without any facility for interacting with the model during the model generation or solution process.In this paper we show how to use the Mosel environment to implement complex algorithms directly in the modelling language.The Office cleaning problem is solved by a branch-and-cut algorithm, implemented entirely in the modelling language (including the definition of the callback function for the solver). Secondly, a cutting stock problem is solved by column generation, also implemented in the modelling language.AMS classification: 90Cxx, 65K05, 68N15     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20