This paper presents the approach that we developed to solve the ROADEF 2003 challenge problem. This work is part of a research program whose aim is to study the benefits and the computer-aided generation of hybrid solutions that mix constraint programming and meta-heuristics, such as large neighborhood search (LNS). This paper focuses on three contributions that were obtained during this project: an improved method for propagating Hamiltonian chain constraints, a fresh look at limited discrepancy search and the introduction of randomization and de-randomization within our combination algebra. This algebra is made of terms that represent optimization algorithms, following the approach of SALSA [1], which can be generated or tuned automatically using a learning meta-strategy [2]. In this paper, the hybrid combination that is investigated mixes constraint propagation, a special form of limited discrepancy search and large neighborhood search.

The recourse to operation research solutions has strongly increasedthe performances of scheduling task in the High-Level Synthesis(called hardware compilation). Scheduling a whole program is notpossible as too many constraints and objectives interact. We decomposehigh-level scheduling in three steps. Step 1: Coarse-grain schedulingtries to exploit parallelism and locality of the whole program (inparticular in loops, possibly imperfectly nested) with a rough view ofthe target architecture. This produces a sequence of logical steps,each of which contains a pool of macro-tasks. Step 2: Micro-schedulingmaps and schedules each macro-task independently taking into accountall peculiarities of the target architecture. This produces areservation table for each macro-task. Step 3: Fine-grain schedulingrefines each logical step by scheduling all its macro-tasks. Thispaper focuses on the third step.As tasks are modeled as reservation tables, we can express resourceconstraints using dis-equations (i.e., negations of equations). Asmost scheduling problems, scheduling tasks with reservation tables tominimize the total duration is NP-complete. Our goal here is todesign different strategies and to evaluate them, on practicalexamples, to see if it is possible to find optimal solution inreasonable time. The first algorithm is based on integer linearprogramming techniques for scheduling, which we adapt to our specificproblem. Our main algorithmic contribution is an exactbranch-and-bound algorithm, where each evaluation is accelerated byvariant of Dijkstra's algorithm. A simple greedy heuristic is alsoproposed for comparisons. The evaluation and comparison are done onpieces of scientific applications from the PerfectClub and theHLSynth95 benchmarks. The results demonstrate the suitability of thesesolutions for high-level synthesis scheduling.

This paper studies the existence and the order structure of strong Berge equilibrium, a refinement of Nash equilibrium, for games with strategic complementarities à la strong Berge. It is shown that the equilibrium set is a nonempty complete lattice. Moreover, we provide a monotone comparative statics result such that the greatest and the lowest equilibria are increasing.

We consider a stochastic approach in order to define an equilibrium model for a traffic-network problem. In particular, we assume a Markovian behaviour of the users in their movements throughout the zones of the traffic area. This assumption turns out to beeffective at least in the context of urban traffic, where, in general, the users tend to travel by choosing the path they find more convenient and not necessarily depending on thealready travelled part.The developed model is a homogeneous Markov chain, whosestationarydistributions (if any) characterize the equilibrium.

In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum solutions for all testedinstances. The semidefinite relaxation gives a lower bound $\frac{C}{W}$ and each heuristic produces a cut S with a ratio $\frac{c_S}{w_S}$, where either cS is at most a factor of C or wS is at least a factor of W. We solved the semidefinite relaxation using a semi-infinite cut generation with a commercial linear programming package adapted to the sparsest cut problem. We showed that the proposed strategy leads to a better performance compared to the use of a known semidefinite programming solver.

A cooperative game is defined as a set of players and a cost function. The distribution of the whole cost between theplayers can be done using the core concept, that is the set of all undominated cost allocations which prevent playersfrom grouping. In this paper we study a game whose cost function comes from the optimal solution of a linear integercovering problem. We give necessary and sufficient conditions for the core to be nonempty and characterize itsallocations using linear programming duality. We also discuss a special allocation, called the nucleolus. Wecharacterize that allocation and show that it can be computed in polynomial time using a column generation method.

Let μ and ν be two probability measures on the real line and let c be a lower semicontinuous function on the plane. The mass transfer problem consists in determining a measure ξ whose marginals coincide with μ and ν, and whose total cost ∫∫ c(x,y)dξ(x,y) is minimum. In this paper we present three algorithms to solve numerically this Monge-Kantorovitch problem when the commodity being shipped is one-dimensional and not necessarily confined to a bounded interval . We illustrate these numerical methods and determine the convergence rate.

Nous construisons des familles de facettes du polytope du sac-à-dos quadratique en 0-1 selon les deux approches suivantes.Le Boolean quadric polytope (introduit dans le cas sans contraintes par Padberg [12]) contenant le polytope du sac-à-dos quadratique, une première approche consiste à se demander sous quelles conditions une facette du premier est aussi une facette du second et quand ces conditions ne sont pas remplies quels liftings permettent d'en faire une facette. Des réponses à ces questions sont données dans le cas de l'inégalité "coupe" introduite par Padberg.Dans une seconde approche, suivant la méthode de linéarisation d'Adams et Sherali [1], nous multiplions par une variable directe ou complémentée une facette du polytope du sac-à-dos linéaire. Nous montrons que cette approche permet d'obtenir des facettes du polytope du sac-à-dos quadratique et nous l'étendons par la suite à la multiplication de facettes du sac-à-dos quadratique lui-même.Des résultats numériques illustrent la mise en oeuvre dans un algorithme de coupes, d'inégalités ainsi obtenues.

Dans cet article, nous proposons une nouvelle méthode de purification pour les problèmes de complémentarité linéaire, monotones. Cette méthode associe à chaque itéré de la suite, générée par une méthode de points intérieurs, une base non nécessairement réalisable. Nous montrons que, sous les hypothèses de complémentarité stricte et de non dégénérescence, la suite des bases converge en un nombre fini d'itérations vers une base optimale qui donne une solution exacte du problème. Le procédé adopté sert également à préconditionner l'algorithme de gradient conjugué lors du calcul de la direction de Newton.

Cet article décrit une approche de la modélisation d'un système d'acteurs, particulièrement adaptée à la modélisation desentreprises, fondée sur la théorie des jeux [11] et sur l'optimisation par apprentissage du comportement de ces acteurs. Cette méthode repose sur la combinaison de trois techniques : la simulation par échantillonnage (Monte-Carlo), la théorie des jeux pour ce qui concerne la recherche d'équilibre entre les stratégies, et les méthodes heuristiques d'optimisation locale, en particulier les algorithmes génétiques. Cette combinaison n'est pas originale en soi, même si elle est rarement utilisée avec toute la puissance d'expression conjointe de ces techniques. La contribution de cet article est double : d'une part nous proposons un modèle qui permet de structurer de façon systématique cette collaboration entre différentes techniques et, d'autre part, nous utilisons la technique des algorithmes génétiques pour enrichir la recherche des équilibres de Nash sous forme de points fixes. Il s'agit d'une méthode de simulation, qui n'est pas destinée à la résolution de problèmes, mais à la validation et l'étude des propriétés d'un modèle associé à un problème particulier.

Let X and Y be two compact spaces endowed withrespective measures μ and ν satisfying the condition µ(X) = v(Y). Let c be a continuous function on the product space X x Y. The mass transfer problem consists in determining a measure ξ onX x Y whose marginals coincide with μ and ν, and such thatthe total cost ∫ ∫ c(x,y)dξ(x,y) be minimized. We firstshow that if the cost function c is decomposable, i.e., can berepresented as the sum of two continuous functions defined on X andY, respectively, then every feasible measure is optimal. Conversely,when X is the support of μ and Y the support of ν and whenevery feasible measure is optimal, we prove that the cost function isdecomposable.

The multiparametric 0-1-Integer Programming (0-1-IP)problem relative to the objective function is a family of 0-1-IP problemswhich are relatedby havingidentical constraint matrix and right-hand-sidevector. In this paper we present an algorithm to perform a completemultiparametric analysis relative to a generalized min max objectivefunction such that the min sum and min max are particular cases.