Cahiers du GERAD par année

Liste chronologique

Recherche

65 Cahiers pour l'année 1991

, et

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
, , , et

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
, , et

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
, et

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
et

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
et

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
, , et

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
, et

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
, et

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
, , et

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
, et

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
, et

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
, et

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
et

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
, et

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
et

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
, et

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
et

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
et

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
et

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
et

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
, et

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 BibTeX

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 BibTeX
et

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
, et

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 BibTeX

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
et

Infinitesimal Perturbation Analysis (IPA) is perhaps the most efficient derivative estimation method for many practical discrete-event stochastic systems, w...

référence BibTeX
, et

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 BibTeX
et

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
, et

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
, et

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
, , et

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 BibTeX
, , , , et

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
, et

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
et

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
et

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
et

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
et

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
et

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
et

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
et

In this paper, we present decomposition algorithms for the solution of large scale stochastic dynamic problems, with convergence results and implementation ...

référence BibTeX
et

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
, , , et

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
et

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
, et

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
, , et

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
, , , et

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
et

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