We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting objective functions. Solving this optimal control problem, optimally, is impossible. Therefore, a discrete-time approximation technique is applied to solve the original multi-objective optimal control problem, using goal attainment method. To show the advantages of the proposed technique, we also develop a Simulated Annealing (SA) algorithm to solve the problem, and compare the discrete-time approximation results against the SA and also the genetic algorithm results.

We describe an interior point algorithm for convex quadratic problem with astrict complementarity constraints. We show that under some assumptions theapproach requires a total of $O(\sqrt{n}L)$ number of iterations, where Lis the input size of the problem. The algorithm generates a sequence of problems, each of which isapproximately solved by Newton's method.

In this paper, we examine the influence of approximate first and/orsecond derivatives on the filter-trust-region algorithm designed forsolving unconstrained nonlinear optimization problems and proposed byGould, Sainvitu and Toint in [12]. Numericalexperiments carried out on small-scaled unconstrained problems fromthe CUTEr collection describe the effect of the use ofapproximate derivatives on the robustness and the efficiency of thefilter-trust-region method.

In this paper, we develop the concept of almost stochastic dominance for higher orderpreferences and investigate the related properties of this concept.

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût, et qui requièrent la mise en œuvre d'un processus d'agrégation. Nous en déduisons diverses heuristiques que nous testons.

In this paper we study bi-directional nearness in a network based on AHP (Analytic Hierarchy Process) and ANP(Analytic Network Process). Usually we use forward (one-dimensional) direction nearness based on Euclidean distance.Even if the nearest point to i is point j, the nearest point to j is not necessarily point i. Sowe propose theconcept of bi-directional nearness defined by AHP'ssynthesizing of weights “for” direction and “from” direction.This concept of distance is a relative distance based on the configuration ofthe set of points located on a plane ornetwork. In order to confirm the usefulness of our study we apply the proposed nearness to solving methods of TSP(Traveling Salesman Problem), where to find an approximate solution of TSP we improved Nearest-Neighbor Method.Some numerical experiments of TSP were carried out. To decide a nearest point we used two kind of nearness, forwarddirection nearness and bi-directional nearness. As a result, by using bi-directional nearness,we obtained goodapproximate solution of TSP. Moreover, the relation between AHP and ANP, through an example, is considered.

In previous papers, we used a Markovian model to determine the optimal functioning rules of a distributed system in various settings. Searchingoptimal functioning rules amounts to solve an optimization problemunder constraints. The hierarchy of solutions arising from the above problem is called the “first order hierarchy”, and may possibly yield equivalent solutions. The present paper emphasizes a specific technique for deciding between two equivalent solutions, which establishes the“second order hierarchy”.

Le Problème du Vendeur m-Péripatétique (m-PVP) est défini sur un graphe non orienté G=(V,E) où V = {1,...,n} est l'ensemble des sommets, E = {(i,j) : i,j ∈ V,i < j} est l'ensemble des arêtes et (cij) est une matrice de coûts définie sur E.Le m-PVP consiste à déterminer m cycles hamiltoniens sur G n'ayant aucune arête en commun et dont le coût total est minimal.Cet article décrit sept nouvelles heuristiques pour le m-PVP et les compare à celle qui a été proposée par Krarup en 1975.

Given a weighted undirected graph G = (V,E),a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of G. Arkin, Halldórsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Könemann, Konjevod, Parekh, and Sinha (2003) study the linear programming relaxations and improve both factors to 3. We describe in the first part of the paper a 2-approximation algorithm for the metric case of tree cover.In the second part, we will consider a generalized version of tree (resp. tour) covers problem which is to find a minimum tree (resp. tours) which covers a subset D ⊆ E of G.We show that the algorithms of Könemann et al.can be adapted for the generalized tree and tours covers problem with the same factors.

We first motivate and define a notion of asymptoticdifferential approximation ratio. For this, we introduce a new class ofproblems called radial problems including in particular the hereditaryones. Next, we validate the definition of the asymptotic differentialapproximation ratio by proving positive, conditional and negativeapproximation results for some combinatorial problems. We first derive adifferential approximation analysis of a classical greedy algorithm forbin packing, the “first fit decreasing”. Next we deal with minimumvertex-covering-by-cliques of a graph and the minimumedge-covering-by-complete-bipartite-subgraphs of a bipartite graph anddevise a differential-approximation preserving reduction from the formerto the latter. Finally, we prove two negative differential approximationresults about the ability of minimum vertex-coloring to be approximatedby a polynomial time approximation schema.

This paper deals with the problem of scheduling n tasks on m identical processors in the presence of communication delays. A new approach of modelisation by a decision graph and a resolution by a tabu search method is proposed. Initial solutions are constructed by list algorithms, and then improved by a tabu algorithm operating in two phases. The experiments carried on arbitrary graphs show the efficiency of our method and that it outperformed the principle existent heuristics.

The multiparametric min max 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of min max 0-1-IP problems which are related by having identical constraint matrix and right-hand-side vector. In this paper we present an algorithm to perform a completemultiparametric analysis relative to the objective function.

A hypergraph is Helly if every family of hyperedges of it, formed by pairwiseintersecting hyperedges, has a common vertex. We consider the concepts ofbipartite-conformal and (colored) bipartite-Helly hypergraphs. In the same way asconformal hypergraphs and Helly hypergraphs are dual concepts, bipartite-conformal andbipartite-Helly hypergraphs are also dual. They are useful for characterizing bicliquematrices and biclique graphs, that is, the incident biclique-vertex incidence matrix andthe intersection graphs of the maximal bicliques of a graph, respectively. These conceptsplay a similar role for the bicliques of a graph, as do clique matrices and clique graphs,for the cliques of the graph. We describe polynomial time algorithms for recognizingbipartite-conformal and bipartite-Helly hypergraphs as well as biclique matrices.

This article presents a basic scheme for deriving systematicallya filtering algorithm from the graph properties based representationof global constraints. This scheme is based on thebounds of the graph parameters used in the description ofa global constraint. The article provides bounds for the most commonused graph parameters.

Dans cet article on modélise le système de la pêche de la sardine au Maroc par la méthode de la programmation dynamique. On montre comment les éléments de la programmation dynamique tels que les étapes, états et actions sont utilisés. Le modèle proposé calcule la quantité de sardine à pêcher durant chaque saison de pêche dans le but de maximiser la récolte totale sur un certain nombre de périodes. Des tests, dans le cas déterministe, sont présentés et leurs résultats montrent que l'approche proposée est prometteuse. Notre modèle peut répondre à des problèmes intéressants tels que l'impact d'introduction de nouvelles technologies de pêche, et la détermination des meilleures périodes et dates du repos biologique. Ceci peut être fait par une analyse paramétrique des données appropriées du modèle. Enfin, on mentionne des données sensibles à la validité du modèle et qui nécessitent un traitement spécial.

Let G = (V,E) be a simple undirected graph.A forest F ⊆ E of G is said to be clique-connecting if each tree of F spans a clique of G.This paper adresses the clique-connecting forest polytope.First we give a formulation and a polynomial time separation algorithm. Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope.Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities.

This paper presents a migration strategy for a set of mobile agents (MAs) in order to satisfy customers' requests in a transport network, through a multimodal information system. In this context, we propose an optimization solution which operates on two levels. The first one aims to constitute a set of MAs building their routes, called Workplans. At this level, Workplans must incorporate all nodes, representing information providers in the multimodal network, in order to explore it completely. Thanks to an evolutionary approach, the second level must optimize nodes selection in order to increase the number of satisfied users. The assignment of network nodes to the required services must be followed by a Workplan update procedure in order to deduce final routes paths. Finally, simulation results are mentioned to invoke the different steps of our adopted approach.

One-fund theorem states that an efficient portfolio in a Mean-Variance (M-V) portfolioselection problem for a set of some risky assets and a riskless asset can be representedby a combination of a unique risky fund (tangency portfolio) and the riskless asset. Inthis paper, we introduce a method for which the tangency portfolio can be produced as acorner portfolio. So, the tangency portfolio can be computed easily and fast by anyalgorithm designed for tracing out the M-V efficient frontier via computing the cornerportfolios. Moreover, we show that how this method can be used for tracing out the M-Vefficient frontier when problem contains a riskless asset in which the borrowing is notallowed.

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want tominimize the number of distinct n-uples of colors used to color a givenset of n-complete-subgraphs of a graph. We will propose two relaxations based onSemi-Definite Programming models for graph and hypergraphcoloring, to approximate those (generally) NP-hard problems, as well asa generalization of the works of Karger et al. for hypergraph coloring,to find good feasible solutions with a probabilisticapproach.

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45),which has been designed to solve constraint satisfaction problems (CSP), canbe seen, either (i) as an extension of the classical depth first treesearch algorithm with the introduction of a free choice of the variable towhich to backtrack in case of inconsistency, or (ii) as a localsearch algorithm in the space of the partial consistent variableassignments. or (iii) as a hybridisation between local searchand constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of thevariable to which to backtrack behave well on consistent instances andthat other heuristics behave well on inconsistent ones. They show alsothat, despite its a priori incompleteness, decision repair,equipped with some specific heuristics, can solve within a limited timealmost all the consistent and inconsistent randomly generatedinstances over the whole constrainedness spectrum. In this paper, wediscuss the heuristics that could be used by decisionrepair to solve consistent instances, on the one hand, andinconsistent ones, on the other hand. Moreover, we establish thatsome specific heuristics make decision repair complete.