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.

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.

In this paper we establish necessary as well assufficient conditions for a given feasible point to be a globalminimizer of smooth minimization problems with mixed variables.These problems, for instance, cover box constrained smooth minimizationproblems and bivalent optimization problems. In particular, ourresults provide necessary global optimality conditions for differenceconvex minimization problems, whereas our sufficient conditionsgive easily verifiable conditions for global optimality of variousclasses of nonconvex minimization problems, including the class ofdifference of convex and quadratic minimization problems. Wediscuss numerical examples to illustrate the optimalityconditions

In recent years, the home delivery market has rapidly been growing since customers can purchase a variety of products very easily via Internet. At the same time, however, customers tend to switch from a supplier to another seeking for better service for them. For this reason, it is necessary for suppliers to enclose their customers by means of various kinds of service and strategy. An appointed delivery date of a product ordered by a customer is one of important factors of supplier's services. From the suppliers' point of view, they hope to make the period from the order date to the delivery date as short as possible to increase their customers, but at the same time they prefer to make this period as long as possible since the risk becomes higher that they cannot deliver products to their consumer by the appointed date under the short period appointed date. This study proposes a stochastic model to determine an optimal appointed delivery date for a supplier. For small values of an appointed delivery date L, the probability that a customer purchases the product becomes larger, but the probability of tardiness increases. In contrast, the purchase probability as well as the penalty of tardiness decreases with L. From this point of view, this study formulates the expected profit for a supplier, which is to be maximized as an objective function. Clarified are the conditions under which an optimal appointed delivery date exists for the case where the purchase probability is expressed by a multinomial logit model. Numerical examples are also presented.

Markov Decision Processes (MDPs) are a classical framework forstochastic sequential decision problems, based on an enumerated statespace representation. More compact and structured representations havebeen proposed: factorization techniques use state variablesrepresentations, while decomposition techniques are based on apartition of the state space into sub-regions and take advantage ofthe resulting structure of the state transition graph. We use a familyof probabilistic exploration-like planning problems in order to studythe influence of the modeling structure on the MDP solution. We firstdiscuss the advantages and drawbacks of a graph based representationof the state space, then present our comparisons of two decompositiontechniques, and propose to use a global approach combining both statespace factorization and decomposition techniques. On the explorationproblem instance, it is proposed to take advantage of the naturaltopological structure of the navigation space, which is partitionedinto regions. A number of local policies are optimized within eachregion, that become the macro-actions of the global abstract MDPresulting from the decomposition. The regions are the correspondingmacro-states in the abstract MDP. The global abstract MDP is obtainedin a factored form, combining all the initial MDP state variables andone macro-state “region” variable standing for the different possiblemacro-states corresponding to the regions. Further research ispresently conducted on efficient solution algorithms implementing thesame hybrid approach for tackling large size MDPs.

In this paper we present the image space analysis, based on a general separation scheme, with the aim of studying Lagrangian duality and shadow prices in Vector Optimization. Two particular kinds of separation are considered; in the linear case, each of them is applied to the study of sensitivity analysis, and it is proved that the derivatives of the perturbation function can be expressed in terms of vector Lagrange multipliers or shadow prices.

This paper addresses a one-machine scheduling problem in which the efficiency of the machine is not constant, that is the duration of a task is longer in badly efficient time periods. Each task has an irregular completion cost. Under the assumption that the efficiency constraints are time-periodic, we show that the special case where the sequence is fixed can be solved in polynomial time. The general case is NP-complete so that we propose a two-phase heuristic to find good solutions. Our approach is tested on problems with earliness-tardiness costs.

In this paper we present a method to perform fast simulation oflarge Markovian systems. This method is based on the use of threeconcepts: Markov chain uniformization, event-driven dynamics,and modularity. An application of urban trafficsimulation is presented to illustrate the performance of our approach.

Le problème de planification de techniciens et d'interventions pour les télécommunications (TIST pour Technicians and Interventions Scheduling Problem forTelecommunications) comprend la planification d'interventions et l'affectation d'équipes de techniciens à ces interventions. Chaque intervention est caractérisée, entre autres, par une priorité. L'objectif de ce problème est de séquencer les interventions en tenant compte de leur priorité tout en satisfaisant un ensemble de contraintes comme l'ordre d'exécution de certaines interventions et le nombre minimum de techniciens d'un niveau de compétence donné à affecter à chaque intervention. La résolution de ce problème est centrée sur un algorithme GRASP (Greedy Randomized Adaptive Search Procedure) caractérisé par une mise à jour dynamique des critères de choix des interventions. Pour évaluer la qualité des résultats obtenus par cette approche heuristique, nous présentons également un calcul de bornes inférieures.

This paper presents an application of Multiple Attribute Utility Theory onstrategic choices concerning energy transportation. The environmental assessmentof a network reinforcement strategy is emphasized. Our assessment bringsabout to consider multidimensional variables in MCDM. However, Multi-AttributedUtility Theory (MAUT) cannot, as a practical matter, manage such variables. We therefore work out a methodology to transform multidimensional variablesinto unidimensional ones. We apply it then to a pratical case. From the application, we draw some conclusions on Multi-Attributed Utility Theoryand on its interest for strategic choices dealing with environmental consequences.

In this paper, we study the differentiability of the trajectories of the logarithmic barrier algorithm for a nonlinearprogram when the set Λ* of the Karush-Kuhn-Tucker multiplier vectors is emptyowing to the fact that the constraint qualifications are not satisfied.


Set covering problems are in great use these days, these problems are applied in many disciplines such as crew scheduling problems, location problems, testing of VLSI circuits, artificial intelligence etc. In this paper α-acceptable optimal solution is given for the fuzzy linear fractional set covering problem where fuzziness involved in the objective function. At first the fuzzy linear fractional problem is being converted in to crisp parametric linear fractional set covering problem then a linearization technique is used to obtain an optimal solution to this parametric problem. This optimal solution will also be the fuzzy optimal solution for the original problem. An example is also provided to illustrate the algorithm.

We propose a parallel algorithm which uses bothMonte-Carlo and quasi-Monte-Carlo methods. A detailed analysis of thisalgorithm, followed by examples, shows that the estimator's efficiencyis a linear function of the processor number. As a concrete applicationexample, we evaluate performance measures of a multi-class queueingnetwork in steady state.

The problem of embedding graphs into other graphs is much studied in thegraph theory. In fact, much effort has been devoted to determining theconditions under which a graph G is a subgraph of a graph H, having aparticular structure. An important class to study is the set of graphs whichare embeddable into a hypercube. This importance results from the remarkableproperties of the hypercube and its use in several domains, such as: thecoding theory, transfer of information, multicriteria rule, interconnectionnetworks ...In this paper we are interested in defining two new classes of embeddingtrees into the hypercube for which the dimension is given.

In this paper, we show that the direct semidefinite programming (SDP) bound for thenonconvex quadratic optimization problem over ℓ1 unit ball(QPL1) is equivalent to the optimal d.c. (difference between convex) bound for thestandard quadratic programming reformulation of QPL1. Then we disprove a conjecture aboutthe tightness of the direct SDP bound. Finally, as an extension of QPL1, we study therelaxation problem of the sparse principal component analysis, denoted by QPL2L1. We showthat the existing direct SDP bound for QPL2L1 is equivalent to the doubly nonnegativerelaxation for variable-splitting reformulation of QPL2L1.

In this paper, we face a generalization ofthe problem of finding the distribution of how longit takes to reach a “target” set T of states inMarkov chain. The graph problems of finding the number of paths thatgo from a state to a target set and of finding the n-length path connectionsare shown to belong to this generalization.This paper explores how the statespace of the Markov chain can be reduced by collapsing togetherthose states that behave in the same way for the purposes ofcalculating the distribution ofthe hitting time of T.We prove the existence and the uniqueness of aoptimal projection for this aim which extends the results given in[G. Aletti and E. Merzbach, J. Eur. Math. Soc. (JEMS)8 (2006) 49–75], together with the existence of a polynomial algorithm which reaches this optimum.Some applied examples are presented. Markov complexity is defined an tested onsome classical problems to demonstrate the deeper understanding that ismade possible by this approach.

Ce travail porte sur l'optimisation des lignesd'usinage pour la grande série. Une telle ligne comporte plusieurspostes de travail, chacun étant équipé avec boîtiers multibroches. Unboîtier multibroche exécute plusieurs opérations en parallèle.Lors de la conception en avant-projet, il est nécessaire d'affecter toutes les opérations à des boîtiers etdes postes de travail de sorte à minimiser le nombre de postes et deboîtiers utilisés. Pour ce nouveau problème d'équilibrage des lignesde production, nous proposons une approche de résolution pardécomposition en utilisant des méthodes exactes et heuristiques. Lesrésultats des tests numériques effectués sur des instances prochesdes problèmes réels sont présentés et analysés.

Usual periodic scheduling problems deal with precedence constraints having non-negativelatencies. This seems a natural way for modelling scheduling problems, since task delaysare generally non-negative quantities. However, in some cases, we need to consider edgeslatencies that do not only model task latencies, but model other precedence constraints.For instance in register optimisation problems devoted to optimising compilation, ageneric machine or processor model can allow considering access delays into/fromregisters. Edge latencies may be then non-positive leading to a difficult schedulingproblem in presence of resources constraints. This research result is related to theproblem of periodic scheduling with storage requirement optimisation; its aims is to solvethe practical problem of register optimisation in optimising compilation. We show thatpre-conditioning a data dependence graph (DDG) to satisfy register constraints beforeperiodic scheduling under resources constraints may create circuits with non-positivedistances, resulted from the acceptance of non-positive edge latencies. As a compilerconstruction strategy, it is forbidden to allow the creation of circuits with non-positivedistances during the compilation flow, because such DDG circuits do not guarantee theexistence of a valid instruction schedule under resource constraints. We study twosolutions to avoid the creation of these problematic circuits. A first solution isreactive, it tolerates the creation of non-positive circuit in a first step, and ifdetected in a further check step, makes a backtrack to eliminate them. A second solutionis proactive, it prevents the creation of non-positive circuits in the DDG during theregister optimisation process. It is based on shortest path equations which define anecessary and sufficient condition to free any DDG from these problematic circuits. Thenwe deduce a linear program accordingly. We have implemented our solutions and we presentsuccessful experimental results.

The recourse to operation research solutions has strongly increasedthe performances of scheduling task in the High-Level Synthesis(called hardware compilation). Scheduling a whole program is notpossible as too many constraints and objectives interact. We decomposehigh-level scheduling in three steps. Step 1: Coarse-grain schedulingtries to exploit parallelism and locality of the whole program (inparticular in loops, possibly imperfectly nested) with a rough view ofthe target architecture. This produces a sequence of logical steps,each of which contains a pool of macro-tasks. Step 2: Micro-schedulingmaps and schedules each macro-task independently taking into accountall peculiarities of the target architecture. This produces areservation table for each macro-task. Step 3: Fine-grain schedulingrefines each logical step by scheduling all its macro-tasks. Thispaper focuses on the third step.As tasks are modeled as reservation tables, we can express resourceconstraints using dis-equations (i.e., negations of equations). Asmost scheduling problems, scheduling tasks with reservation tables tominimize the total duration is NP-complete. Our goal here is todesign different strategies and to evaluate them, on practicalexamples, to see if it is possible to find optimal solution inreasonable time. The first algorithm is based on integer linearprogramming techniques for scheduling, which we adapt to our specificproblem. Our main algorithmic contribution is an exactbranch-and-bound algorithm, where each evaluation is accelerated byvariant of Dijkstra's algorithm. A simple greedy heuristic is alsoproposed for comparisons. The evaluation and comparison are done onpieces of scientific applications from the PerfectClub and theHLSynth95 benchmarks. The results demonstrate the suitability of thesesolutions for high-level synthesis scheduling.