We propose a new large scale optimization model, named TS_LAP, for the locomotive assignment problem (LAP), which relies on train strings or consist travel p...

In grid or cloud computing, the optimal location and capacity of data centers (hosting the servers executing the remote users' tasks) depends on the availabl...

This paper discusses a unique formulation of en-route flight planning problem in a constrained airspace with the objective of minimizing the total cost while...

Increase of bandwidth demand in data networks, driven by the continuous growth of the Internet and the increase of bandwidth greedy applications, raise the i...

Avoiding or preventing deadlocks in simulation tools for train scheduling remains a critical issue, especially when combined with the objective of minimizing...

Optical networks, given their excellent characteristics in terms of high bandwidth and low latency, play a crucial role in enabling today's applications that...

We propose a new dynamic row/column management algorithm for the schedule of freight trains in a single/double track railway system. While many works have al...

Shared-segment protection offers a good compromise between shared link and path protection. In this paper, we further investigate segment protection with res...

We study the optimisation of a biomass waste to energy conversion system using an adapted Tabu Search heuristic. It corresponds to a non-linear and non-conv...

Survivability in IP-over-WDM networks has already been extensively discussed in a series of studies. While many studies assume an IP restoration scheme and f...

We determine the threshold herd size at which a biomass waste to energy conversion system becomes commercially viable. The threshold herd size is found by ...

In this paper we address the problem of dimensioning infrastructure, comprising both network and server resources, for large-scale decentralized distributed...

<p> <i>p</i>-Cycles have been extensively studied under a single link failure scenario. Even though not as common, single node failures may occur as well,...

In IP-over-WDM networks, protection can be offered at the optical layer or at the IP layer. Today, it is well acknowledged that synergies need to be develope...

The focus of the paper is on adequate service and content distribution with Dedicated Channels having a Small number of Viewers (DCSV for short) in a multi-c...

We propose a new generic flow formulation for Failure-Independent Path-Protecting (FIPP) <i>p</i>-cycles subject to multiple failures. While our new model re...

With the growing popularity of bandwidth demanding services such as HDTV, VoD, and video conferencing applications, there is an increasing demand on broadb...

The traffic evolution is notoriously marked by an increasing dynamism that promotes the design of a dynamic optical layer. Despite the contention issue, Opti...

The focus of this paper is on the design of the so-called Optical Wide Area Networks (OWANs), i.e., optical networks that cover broad areas. Our objective ...

This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and band...

We consider a multi-layer network design model arising from a real-life telecommunication application where traffic routing decisions imply the installati...

Optical transmission allows massive data transfers thanks to its tremendous transport capacity. Sustained efforts have been made to address the physical co...

Availability requirements in survivable transport networks depend on the type of costumers using the network and the supported services. Nowadays, a variety ...

In today optical WDM networks, capacity expansion is performed by the addition of transport blades (e.g., transceivers) at end nodes of optical fibers. It al...

This paper investigates design methods of protection schemes in survivable WDM networks which use pre-configured protection structures (<i>p</i>-structures) ...

<p>The introduction of new applications that require high bandwidth, high service availability and reliability has generated many researches in the design of...

<p>We propose a new design scheme of resilient Wavelength Division Multiplexing (WDM) networks by extending and reshaping pre-configured protection tree (<i...

<p>Today, OCS (Optical Circuit Switching) is still the only mature technology for optical transfer, even if it suffers from its coarse granularity under dyn...

<p>In this paper, we present a scalable and agile design for next generation optical backbone networks. We assume each node to be equipped with a MultiServic...

The Protected Working Capacity Envelope (PWCE) concept was proposed by Grover (2004) in order to simplify network and operation management in survivable WDM ...

The multi-agent resource allocation problem corresponds to the negotiation of <i>m</i> resources among <i>n</i> autonomous agents, in order to maximize a soc...

Routing for shared protection has received a lot of interest in the last few years. A large number of the studies focus on minimizing the network transport ...

Routing for Overlapping Segment Shared Protection (OSSP) in multi-domain networks is more difficult than that in single domain networks because of the scalab...

We investigate a first column generation (CG) formulation for the design of failure independent path-protecting (FIPP) <i>p</i> -cycle survivable transport ...

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as f...

We present a review of several column generation formulations for the Routing and Wavelength Assignment (RWA) problem with the objective of minimizing the b...

The dynamic routing problem for Overlapped Segment Shared Protection in multi-domain networks has not received a lot of interest so far as it is more difficu...

Convolutional Self-Doubly Orthogonal Codes (CSO²C) have been introduced in 1998 by Haccoun et al. as a novel class of convolutional codes which c...

We study the problem of routing and wavelength assignment (RWA) in a WDM optical network under different hop assumptions, i.e., with and without wavelength ...

We present an exact algorithm for solving the channel assignment problem in cellular telephony networks. This problem consists of assigning sets of channels...

We consider the problem of traffic grooming of low-rate traffic circuits in WDM rings where circuits are associated with a set of heterogeneous granularitie...

Different integer linear programming (ILP) formulations have been proposed for the routing and wavelength assignment problem in WDM optical networks, mainl...

We present a review of column generation formulations for the Routing and Wavelength Assignment (rwa) problem with the objective of minimizing the blocking r...

We present a review of the various integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem i...

We present a review of the various integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem i...

WDM networks offer a technology that can transferred several optical signals into a single optical fiber. This allows for more efficient use of the huge capa...

A Golomb ruler with <i>M</i> marks can be defined as a set {<i>a_i</i>} of integers so that all differences &delta;_<i>ij</i> = <i>a<sub>...

The Golomb Ruler problem consists in finding $n$ integers such that all possible differences are distinct and such that the largest difference is minimum. W...

In this paper we propose a mathematical model for the dimensioning of a 3G multimedia network and design a Tabu Search heuristic to solve it. The model is a...

We define two classes of lower bounds using either one or two simplices for the minimization of a concave function over a polytope. For each of them, a pro...

Consider <i>N</i> entities to be classified (e.g., geographical areas), a matrix of dissimilarity between pairs of entities, a graph <i>H</i> with vertices a...

This paper presents an analysis of the forward link capacity of a cellular network, based on IS-95 CDMA technology. The forward link, or downlink, refers to...

Given a set of logical sentences and probabilities that these sentences are true, the probabilistic logic problem consists in determining whethe...

Given a set of logical sentences together with nonnegative weights assigned to each of them, the Maximum Weight Satisfiability problem (MAX-WEIGHT SAT) cons...

We modify the algorithm of Pardalos and Rodgers [40] for the minimization of a pseudo-boolean quadratic function by introducing an easy to compute lower bou...

The set of equilibrium points of a bimatrix game is the union of polytopes that are not necessarily disjoint. Knowledge of the vertices of these polytopes ...

Clique partitionning in Euclidean space <b>R</b>ⁿ consists in finding a partition of a given set of <i>N</i> points into <i>M</i> clusters in ord...

Mirkin's additive clustering (or qualitative factor analysis) algorithm explains similarities between entities by sequentially finding a cluster of entities...

We study several formulations of the channel assignment problem in an FDMA network as a linear integer 0-1 program. We consider the objective of minimizing...

Given a set of logical sentences and probabilities that these sentences are true, the probabilistic logic problem consists in determining whether these prob...

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin r...

We study the solution of combinatorial problems with the column generation techniques when there is a very large number of both variables and constraints. ...

Treatment of imprecise probabilities within the probabilistic satisfiability approach to uncertainty in knowledge-based systems is surveyed and discussed. ...

Cellular manufacturing is a promising approach for grouping efficiency in manufacturing systems. Although this problem has been extensively studied in the ...

The probabilistic satisfiability problem consists, given <i>m</i> logical sentences, with their probabilities to find if they are coherent, and if it is the...

We discuss the relationship between probabilistic logic and <img src="pi.gif" align=bottom>-CMS. Given a set of logical sentences and probabilities, the ou...

Given a network modeled by a probabilistic graph <i>G =</i> (<i>V,E</i>) with bounds on the operation probabilities of edges and of pairs of edges, the seco...

Solving exactly large instances of the channel assignment problem often requires to solve large linear programs with respect to the number of columns or row...

We present a branch and cut algorithm that yields in finite time, a globally <img src="epsilon.gif" align=bottom>-optimal (with respect to feasibility and o...

An exact algorithm is proposed for minimum sum-of-squares nonhierarchical clustering, i.e., for partitioning a given set of points from Euclidean <i>m</i>-s...

We consider a resource constrained shortest path problem in acyclic graphs, where resource windows are associated with the arcs, while lower and upper thres...

We propose a new finite cone covering algorithm for concave minimization over a polytope, in which the cones are defined by extreme points of the polytope. ...

Non-parametric estimation of smooth functions belonging to Sobolev classes is closely related to the problem of estimating the (infinite dimensional) mean o...

We present branch and bound algorithms that enumerate in finite time all Nash equilibria for strategic and sequence form bimatrix games. For each forms, th...

We present a convergence proof of Tuy's cone splitting algorithm with a pure <img src="omega.gif" align=bottom>-subdivision strategy, for the minimization o...

We consider Nash equilibria as correlated equilibria and apply polyhedral theory to study extreme Nash equilibrium properties. We obtain an alternate proof ...

We propose a 0-1 column generation model for the problem of channel assignment in a cellular network, with the objective of minimizing the unsatisfied chann...

A new algorithm, which exploits information from both ends of the network, is presented for the bicriterion shortest path problem. The algorithm extends eff...

The disjoint bilinear programming problem can be reformulated using two distinct linear maxmin programming problems. There is a simple bijection between the...

A new algorithm, based on interval analysis, is proposed for global optimization of constrained nonlinear nonconvex functions of several variables. It expl...

We present an overview of the exact methods for channel assignment in cellular networks together with a new linear 0-1 column generation formulation. After ...

Cellular networks must be updated very often. Due to technical and economical reasons, the complete channel retuning of an urban network has to be done in ...

We present a new convergence result for the cone partitioning algorithm with a pure <img src="omega.gif" align=bottom>-subdivision strategy, for the minimiz...

We present a 0-1 column generation model for channel block assignment in a cellular network, with the objective of minimizing the interference level. Priori...

We study the set of lower bounds which have been proposed for the numbering of a complete graph. We first show that the computation of most of them can be ...

Cellular networks must be updated very often. Due to technical and economical reasons, the complete channel resetting of an urban network has to be done in...

We propose a greedy heuristic and a Tabu Search type heuristic for channel block assignment subject to co-channel, adjacent channel, co-site constraints as ...

This paper presents a 0 - 1 column generation model with a resource constrained shortest path auxiliary problem for nurse scheduling. The master problem fin...

Given a set of entities, Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. As many types of clusterin...

It is shown that the anytime deduction procedure for probabilistic entailment of Frisch and Haddawy does not have the correctness property when the probabil...

Clustering with a criterion which minimizes the sum of squared distances to cluster centroids is usually done in a heuristic way. An exact polynomial algori...

Two new algorithms are proposed for the problem of positioning a new product in attribute space in order to attract the maximum number of consumers. Each c...

A review is made of models and algorithms for probabilistic satisfiability and its extensions. The basic probabilistic satisfiability problem, in decision f...

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

The maxmin problem models a game sequentially played by two players having opposite objective. Before making his move, the first player must anticipate the...

We present a new method for minimizing the sum of a convex function and a product of <i>k</i> nonnegative convex functions over a convex set. This problem i...

D.-c. programming is a recent technique of global optimization, which allows the solution of problems whose objective function and constraints can be expres...

We study links between the bilevel linear and linear mixed 0-1 programming problems. A new reformulation of the linear mixed 0-1 programming problem into a...

Weber's problem is to locate a facility in order to minimize the sum of its weighted distances to <i>n</i> fixed demand points. On a sphere, this problem i...

Cluster Analysis is at the crossroad of many disciplines, and has numerous and diverse methods and applications. Mathematical Programming (together with gra...

We propose a branch-and-bound framework for the global optimization of unconstrained Hölder functions. The general framework is used to derive two algorithm...

We propose a new exact algorithm for the convex-quadratic bilevel programming problem, i.e, for problems with convex objective function and convex constrain...

Consider an assignment problem in which persons are qualified for some but usually not all of the jobs. Moreover, assume persons belong to given seniority c...

We study the generalization of Piyavskii's algorithm (1972), proposed by Mladineo (1986), for the global optimization of multivariate Lipschitz functions. I...

Global optimization methods aim at finding the global optimum of a nonlinear and nonconvex function subject to nonlinear and nonconvex constraints. The main...

An overview is given, with new results, of mathematical models and algorithms for probabilistic logic, probabilistic entailment and various extensions. Anal...

Given a set of logical sentences together with probabilities that these sentences are true, the probabilistic satisfiability (PSAT) problem consists, in it...

We present a method to compute valid concavity cuts for the linear maxmin programming problem. We consider a primal and a dual approach. In both cases the p...

A new paradigm for cluster analysis is outlined. It is called Sequential Clustering. Given a set <i>O</i> of <i>N</i> entities a best cluster of <i>K</i> ...

Le problème de la satisfaisabilité probabiliste (PSAT) consiste à déterminer, étant donné les probabilités de <i>m</i> événements (ou propositions logiques...

An <i>O</i> (<i>mn</i> log <i>n</i>) labeling algorithm is proposed for minimum sum of diameters bipartitioning of the vertex set of a weighted graph (with ...

Consider a set of logical sentences together with probabilities that they are true. These probabilities must satisfy certain conditions for this system to b...

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

Lipschitz optimization solves global optimization problems in which the objective function and constraint left-hand sides may be given by oracles (or explic...

Much work has been devoted to the problem of finding maximum likelihood estimators for the three-parameter Weibull distribution. This problem has not been c...

The minimum sum-of-stars (or <i>p</i>-median, or <i>p</i>-medianoïd) clustering problem consists in partitioning a given set of entities into <i>P</i> clust...

Three main mathematical programming approaches have been followed to design exact algorithms for partitioning problems in cluster analysis, cutting-planes, ...

Dendrograms are widely used to represent graphically the clusters and partitions obtained with hierarchical clustering schemes. Espaliers are generalized de...

We propose a new coding algorithm (called NTUPLE) for computing the N-tuple code (due to Knop et al.) for chemical trees. The algorithm NTUPLE has a ti...

A linear algorithm is proposed for a particular case of the satisfiability problem which strictly includes nested satisfiability. Recognition of this case c...

We propose a new branch-and-bound algorithm for the Satisfiability problem (SAT). A relaxation as well as a decomposition scheme are defined by using polyno...

Consider a set <i>O</i> of <i>N</i> entities and a matrix <i>D</i> = (<i>d_{k <img src="ell.gif">}</i>) of dissimilarities between pairs of entities...

In a previous paper, a global optimization algorithm, called MLEW, is provided for finding Maximum Likelihood Estimators for the three-parameter Weibull dis...

We consider nonlinear programs in 0-1 variables with nonlinear constraints and survey the main approaches to their solution: (i) linearization; (ii) algebra...

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

Ce document explique comment réaliser une implantation efficace d'une méthode d'énumération implicite avec une stratégie du type le meilleur d'abord. Dans l...

The off-line vertex enumeration problem for polytopes consists in determining all vertices of a given polytope <i>P</i>. The on-line vertex enumeration prob...

We consider the problem of minimizing the weighted sum of earliness and tardiness of jobs scheduled around a common due date, <i>d</i>. The weight of a job ...

A recent global optimization algorithm using decomposition (GOP), due to Floudas and Visweswaran, when specialized to the case of polynomial functions is sh...

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 many manufacturing systems, parts must be fed to automatic machines in a specific orientation. This is often accomplished by what are known as part orien...

There has been much recent statistical research in the area of inference under constraints. Here we consider the problem of bounded parameter estimation, in...

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

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

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

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

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

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

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

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

Nilsson recently introduced a rigorous semantic generalization of logic in which the truth values of sentences are probability values. This led to state pre...

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational te...

Timonov proposes an algorithm for global maximization of univariate Lipschitz functions in which successive evaluation points are chosen in order to ensure ...

Divisive hierarchical clustering algorithms with the diametercriterion proceed by recursively selecting the cluster with largest diameter and partitioning i...

We study the complexity and propose an algorithm for the problem of determining, given <i>p</i> vectors of {-1, 1}<i>ⁿ</i>, all linear combinatio...

Consider <i>N</i> entities to be classified, with given weights, and a matrix of dissimilarities between pairs of them. The split of a cluster is the small...

Several authors have proposed to estimate Lipschitz constants in global optimization by a multiple of the largest slope (in absolute value) between successi...

We show that the satisfiability and maximum satisfiability problems can be transformed into set covering problems at the expense of acceptable increase of s...

We propose a new algorithm to solve the on-line vertex enumeration problem for polytopes, doing all computations in <i>n</i>-space, where <i>n</i> is the di...

We consider the following global optimization problems for a Lipschitz function <i>f</i> implicitly defined on an interval [<i>a,b</i>]. Problem <i>P'</i>:...

We consider the following global optimization problems for a univariate Lipschitz function <i>f</i> defined on an interval [<i>a,b</i>]: Problem <i>P</i>: f...

FORTRAN code of an efficient implementation of a <img src="Theta.gif" align=bottom> (<i>N</i>₂) algorithm for the maximum sum-of-splits clusterin...

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local opti...

Piyavskii's algorithm maximizes a univariate function <i>f</i> satisfying a Lipschitz condition. We compare the numbers of iterations needed to obtain a bou...

Consider <i>N</i> entities to be classified, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity be...

We study the design problem of part-orienting systems which are often employed in many manufacturing environments to orient parts of assembly or to perform o...

The Basic Algorithm of pseudo-Boolean programming due to Hammer and Rudeanu allows to minimize nonlinear 0-1 functions by recursively eliminating one variabl...

An experimental computer system for globally optimal design, called BAGOP, is discussed. This new tool uses the computer alebra system MACSYMA to implement ...

Many problems of globally optimal design have been solved in the literature using monotonicity analysis and a variety of tests applied in an ad hoc way. The...

Many problems of globally optimal design have been solved by using monotonicity analysis. New monotonicity principles are obtained by exploiting non strict ...

Ordered sequential algorithms for the global minimization of univariate functions over an interval proceed by evaluating this function at successive points c...

Consider N entities to be classified, and a matrix of diffimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an...

A decomposition method is proposed for minimizing quadratic pseudoboolean functions. The result is: minimum of <i>f</i> = &#x2211;^p<sub><i>i</i>=...

Old and new algorithms for the Maximum Satisfiability problem are studied. We first summarize the different heuristics previously proposed, i.e. the approxi...