65 Cahiers pour l'année 1991
Mixed-Integer Column Generation Algorithms and the Probabilistic Maximum Satisfiability Problem
The column generation approach to large-scale linear programming is extended to the mixed-integer case. Two general algorithms, a dual and a primal one, are...
référence BibTeX
This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set ...
référence BibTeX
The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maxi...
référence BibTeX
The purpose of this paper is to formulate and solve an optimization problem arising in the operations of a numerical control machine such as a punch press. ...
référence BibTeX
One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time-changing information even in ...
référence BibTeX
We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation ...
référence BibTeX
This paper presents the development of a new optimal dynamic programming algorithm for the minimization of the total traveling cost for the traveling salesm...
référence BibTeX
An exact algorithm is proposed for average-linkage divisive hierarchical clustering, i.e., at each level of the hierarchy a cluster is bipartitioned in such...
référence BibTeX
In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under thr...
référence BibTeX
It is an old observation that for the Generalized Assignment Problem (GAP) a Linear Programming (LP) relaxation introduces only few fractions in the solutio...
référence BibTeX
A hexagonal system is a connected plane graph without cut vertices in which each interior face is a regular hexagon. A linear algorithm is proposed to find ...
référence BibTeX
Weber's problem consists in locating a facility in the plane in such a way that the weighted sum of Euclidean distances to <i>n</i> given points be minimum....
référence BibTeX
In a first attempt to explain the good behavior of local improvement heuristics (such as Tabu Search and Simulated Annealing) for the <i>k</i>-coloring prob...
référence BibTeX
Approaches like infinitesimal perturbation analysis and the likelihood ratio method have drawn a great deal of attention recently, as ways of estimating the...
référence BibTeX
A branch-and-bound algorithm is proposed for global minimization of indefinite quadratic functions subject to box constraints. Branching is done according ...
référence BibTeX
Given a two-way contingency table in which the rows and columns both define ordinal variables, the parameters are estimated by maximizing the likelihood fun...
référence BibTeX
The lattice structure of conventional linear congruential random number generators (LCGs), over integers, is well known. In this paper, we study LCGs in the...
référence BibTeX
Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. Such bounds for the function,...
référence BibTeX
We derive from Boolean methods a transformation which, when it can be applied, builds from a graph <i>G =</i> (<i>V,E</i>) a new graph <i>G'=</i> (<i>V',E'<...
référence BibTeX
A multiregional electricity supply and trading model, derived from MARKAL and involving four regions, is used to assess the advantages derived from a cooper...
référence BibTeX
A new heuristic algorithm, based on the Tabu Search methodology, is proposed for constrained redundancy optimization in series and in complex systems. It h...
référence BibTeX
We describe two new classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedu...
référence BibTeX
Consider a network facility location problem where congestion arises at facilities, and is represented by delay functions that approximate the queuing proce...
référence BibTeX
For a weighted graph <i>G =</i> (<i>V,E</i>), the maximum weighted <i>k</i>-coloring problem is to color a set of vertices of maximum weight using <i>k</i> ...
référence BibTeX
Layout planning is an appropriate area in which to apply optimization models. A method is proposed here for evaluating general layouts (block layouts) when ...
référence BibTeX
We consider the directed graph representing the obstruction relation between objects moving along the streamlines of a two-dimensional velocity field. A col...
référence BibTeX
We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functi...
référence BibTeX
We present a new class of change in risk, which includes several previous ones (price squeeze, strong increase in risk of Meyer and Ormiston) and leads to u...
référence BibTeX
A hexagonal system is a connected plane graph without cut vertices in which each interior face is a regular hexagon. A linear algorithm is proposed to find ...
référence BibTeX
Konno and Inori (1989) have recently proposed two flexible models for bond portfolio optimization, together with heuristics to solve them. It is shown that ...
référence BibTeXIndice de concentration et statistique de Kolmogorov, application à des distributions de revenu
On présente, à l'aide d'un modèle probabiliste, une approximation d'un indice de concentration d'un nuage de points dans <b>R</b>. Ce modèle conduit à établ...
référence BibTeXOpenshops with Jobs Overlap
We consider the complexity status of scheduling <i>n</i> jobs in an openshop with <i>m</i> machines, when overlapping of jobs is permitted, for some classic...
référence BibTeX
Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such red...
référence BibTeX
La programmation linéaire généralisée peut être étendue au cas des programmes mixtes en utilisant seulement l'algorithme primal révisé du simplexe en variab...
référence BibTeXCriteria for the Ergodicity of Hedging Point Control Policies in Single Part Manufacturing Systems
The Markov renewal viewpoint of single part manufacturing systems under hedging point control policies, subjected to a constant demand for parts rate, is us...
référence BibTeX
Infinitesimal Perturbation Analysis (IPA) is perhaps the most efficient derivative estimation method for many practical discrete-event stochastic systems, w...
référence BibTeX
The purpose of this paper is to describe a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algori...
référence BibTeX
A new branch-and-bound algorithm for linear bilevel programming is proposed. Necessary optimality conditions expressed in terms of tightness of the follow...
référence BibTeXA linear Time Algorithm for the Computation of Some Distance Functions Between Convex Polygons
We present in this paper a linear time algorithm for the computation of some distance functions between convex polygons in R<sup>2</sup> in the general case...
référence BibTeX
We present algorithms for computing some distance functions between two (possibly intersecting) polygons, both in the convex and nonconvex cases. The inter...
référence BibTeX
A bounded vertex coloring of a graph <i>G</i> is a usual vertex coloring in which each color is used at most <i>k</i> times (where <i>k</i> is a given numbe...
référence BibTeX
The interaction between a utility company and electricity cogenerators is modeled via a game theoretic, systems analysis approach, under the assumption of a...
référence BibTeX
This paper deals with the implementation of the interior point cutting plane algorithm of Goffin-Haurie-Vial, with a special application to the solution of ...
référence BibTeXCanadian MARKAL: An advanced Linear Programming System for Energy and Environmental Modelling
In this paper, we report on an updated, improved version of the MARKAL energy model, developed in the late 1970's under the aegis of member countries of the...
référence BibTeX
The Airline Crew Scheduling Problem can be defined as the problem of finding a set of feasible rotations so that the total cost is minimum and all the fligh...
référence BibTeX
The (<b>R</b>,max,+) algebra gives raise, to a "linear algebra" very usefull in the context of DEDS which can be represented by envent graphs. Some propert...
référence BibTeX
This paper deals with a stochastic programming model which complements long range market simulation models such as those currently developed by several gas ...
référence BibTeX
A manager planning a distribution network faces a multiple-vehicle routing problem. The first step is to assign customers to vehicles. One way to do this is...
référence BibTeX
We consider the problem of determining a hyperplane that separates, as "well" as possible, two finite sets of points in <i>R<sup>n</sup></i>. We analyze two...
référence BibTeX
This paper presents a new heuristic for the Euclidean planar traveling salesman problem. The heuristic takes advantage of the natural alignment of the point...
référence BibTeX
We propose in this paper new approximate algorithms for the Minimum Rectilinear Steiner Tree problem, based on a two-point-connection strategy. We also pres...
référence BibTeX
A semilattice <i>S</i> is an associative, commutative and idempotent binary operation on a set. The product <i>xy</i> then corresponds to the least upper bo...
référence BibTeX
We prove a planarity-independent analogue of a theorem of Nowakowski, Rival and Urrutia concerning lattices contained in orders representable as blocking re...
référence BibTeX
A notion of Nash equilibrium, called event-adapted equilibrium, is defined for non-cooperative, multi-stage games where uncertainty is gradually resolved. ...
référence BibTeX
In this paper, we present decomposition algorithms for the solution of large scale stochastic dynamic problems, with convergence results and implementation ...
référence BibTeXApplication of Stochastic Programming to Medium and Long Term Planning in the Refining Industry
The refining industry is faced with medium and long term planning problems (e.g. crude supply, stocks, capacity decisions) where an important part of the da...
référence BibTeX
In this paper, we deal with the problem of sequencing parts and robot moves in a robotic cell where the robot is used to feed machines in the cell. The robo...
référence BibTeX
This paper describes a domain criterion for a multicriteria problem, given a single decision maker. It then outlines possibilities for aggregating individua...
référence BibTeX
We analyze the vehicle routing problem with constraints on the total distance traveled by each vehicle. Two objective functions are considered: minimize t...
référence BibTeX
We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process ...
référence BibTeX
L'algèbre (max, +) est un outil important en Recherche Opérationnelle et en Automatique dans le contexte de l'analyse des systèmes à événements discrets. L'...
référence BibTeX
In this article, a MARKAL model of electricity trading between four regions is presented and used to simulate the advantages derived from cooperative planni...
référence BibTeX
In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with rest...
référence BibTeX
Among orders that arise from obstructions between geometric or abstract objects, certain lattices and lattice-like structures appear distinctively. This pap...
référence BibTeX
It is proved that for any hexagonal system, there is a peak and a valley which are border adjacent (the path from the peak to the valley along the border is...
référence BibTeX