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...

This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set ...

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...

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. ...

One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time-changing information even in ...

We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation ...

This paper presents the development of a new optimal dynamic programming algorithm for the minimization of the total traveling cost for the traveling salesm...

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...

In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under thr...

It is an old observation that for the Generalized Assignment Problem (GAP) a Linear Programming (LP) relaxation introduces only few fractions in the solutio...

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 ...

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....

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...

Approaches like infinitesimal perturbation analysis and the likelihood ratio method have drawn a great deal of attention recently, as ways of estimating the...

A branch-and-bound algorithm is proposed for global minimization of indefinite quadratic functions subject to box constraints. Branching is done according ...

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...

The lattice structure of conventional linear congruential random number generators (LCGs), over integers, is well known. In this paper, we study LCGs in the...

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

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'<...

A multiregional electricity supply and trading model, derived from MARKAL and involving four regions, is used to assess the advantages derived from a cooper...

A new heuristic algorithm, based on the Tabu Search methodology, is proposed for constrained redundancy optimization in series and in complex systems. It h...

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...

Consider a network facility location problem where congestion arises at facilities, and is represented by delay functions that approximate the queuing proce...

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> ...

Layout planning is an appropriate area in which to apply optimization models. A method is proposed here for evaluating general layouts (block layouts) when ...

We consider the directed graph representing the obstruction relation between objects moving along the streamlines of a two-dimensional velocity field. A col...

We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functi...

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...

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 ...

Konno and Inori (1989) have recently proposed two flexible models for bond portfolio optimization, together with heuristics to solve them. It is shown that ...

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...

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...

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such red...

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...

The Markov renewal viewpoint of single part manufacturing systems under hedging point control policies, subjected to a constant demand for parts rate, is us...

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

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...

A new branch-and-bound algorithm for linear bilevel programming is proposed. Necessary optimality conditions expressed in terms of tightness of the follow...

We present in this paper a linear time algorithm for the computation of some distance functions between convex polygons in R² in the general case...

We present algorithms for computing some distance functions between two (possibly intersecting) polygons, both in the convex and nonconvex cases. The inter...

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...

The interaction between a utility company and electricity cogenerators is modeled via a game theoretic, systems analysis approach, under the assumption of a...

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 ...

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...

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...

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...

This paper deals with a stochastic programming model which complements long range market simulation models such as those currently developed by several gas ...

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...

We consider the problem of determining a hyperplane that separates, as "well" as possible, two finite sets of points in <i>Rⁿ</i>. We analyze two...

This paper presents a new heuristic for the Euclidean planar traveling salesman problem. The heuristic takes advantage of the natural alignment of the point...

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...

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...

We prove a planarity-independent analogue of a theorem of Nowakowski, Rival and Urrutia concerning lattices contained in orders representable as blocking re...

A notion of Nash equilibrium, called event-adapted equilibrium, is defined for non-cooperative, multi-stage games where uncertainty is gradually resolved. ...

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

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...

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...

This paper describes a domain criterion for a multicriteria problem, given a single decision maker. It then outlines possibilities for aggregating individua...

We analyze the vehicle routing problem with constraints on the total distance traveled by each vehicle. Two objective functions are considered: minimize t...

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 ...

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'...

In this article, a MARKAL model of electricity trading between four regions is presented and used to simulate the advantages derived from cooperative planni...

In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with rest...

Among orders that arise from obstructions between geometric or abstract objects, certain lattices and lattice-like structures appear distinctively. This pap...

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...