On the Pallet Loading Problem
On the solution of traveling salesman problems.
On the Steiner 2-edge connected subgraph polytope
In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to...
On the structure of the quadratic Boolean problem polytope
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
Online LIB problems : heuristics for bin covering and lower bounds for bin packing
We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...
Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...
Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
Optimality-preserving elimination of linearities in Jacobian accumulation.
Optimisation globale par stratégie d'évolution
Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions
Nous nous intéressons dans cet article au problème de découpe guillotine en deux dimensions noté 2BP/O/G. Il s'agit de découper un certain nombre de pièces rectangulaires dans un ensemble de plaques de matière première, elles même rectangulaires et identiques. Celles-ci sont disponibles en quantité illimitée. L'objectif est de minimiser le nombre de plaques utilisées pour satisfaire la demande, en appliquant une succession de coupes, dites guillotines, allant de bout en bout. Nous proposons une approche...
Optimization of an SMD placement machine and flows in parametric networks
In the minimization of the number of subtours made by the insertion head of an SMD placement machine a variant of the network flow problem arose. In a network with vertices and arcs a set of arcs (parametrized arcs) is given. The task is to find a flow of a given size such that the maximum of flow values along the arcs from is minimized. This problem can be solved by a sequence of maximum flow computations in modified networks where the capacities of the parametrized arcs are successively...
Optimization of touristic distribution networks using genetic algorithms.
The eight basic elements to design genetic algorithms (GA) are described and applied to solve a low demand distribution problem of passengers for a hub airport in Alicante and 30 touristic destinations in Northern Africa and Western Europe. The flexibility of GA and the possibility of creating mutually beneficial feed-back processes with human intelligence to solve complex problems as well as the difficulties in detecting erroneous codes embedded in the software are described. A new three-parent...
Ordres médians et ordres de Slater des tournois
Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.
Original title unknown
Planification à moyen terme de la production d'un satellite défilant et ensembles stables
Polynomially solvable traveling salesman problems
Práce Vojtěcha Jarníka v kombinatorické optimalizaci
Preface
Préférences et rationalité stochastiques
Le but de cet article est de procéder à une présentation pédagogique d'un concept étendu de rationalité, la rationalité stochastique. Dans une première partie, nous exposons le problème à l'aide d'un exemple simple et posons un ensemble de définitions préliminaires. Puis, dans une seconde partie, nous présentons le résultat fondamental de Falmagne (1978) s'appliquant aux situations de choix multiples ; l'approche ensembliste de cet auteur est formalisée à partir du concept de polynômes de Block-Marschak...