The purpose of this article is to show the great interest of theuse of propagation (or pruning) techniques, inside classicalinterval Branch-and-Bound algorithms. Therefore, a propagationtechnique based on the construction of the calculus tree isentirely explained and some properties are presented without theneed of any formalism (excepted interval analysis). This approachis then validated on a real example: the optimal design of anelectrical rotating machine.

In this paper, information theoretic methodology forsystem modeling is applied to investigate the probability density functionof the busy period in M/G/1 vacation models operating under the N-, T- andD-policies. The information about the density function is limited to a fewmean value constraints (usually the first moments). By using the maximumentropy methodology one obtains the least biased probability densityfunction satisfying the system's constraints. The analysis of the threecontrollable M/G/1 queueing models provides a parallel numerical study ofthe solution obtained via the maximum entropy approach versus “classical”solutions. The maximum entropy analysis of a continuous system descriptor(like the busy period) enriches the current body of literature which, inmost cases, reduces to discrete queueing measures (such as the number ofcustomers in the system).

We propose a variational model for one of the most importantproblems in traffic networks, namely, the network equilibrium flow that is, traditionallyin the context of operations research, characterized by minimum cost flow. This model has the peculiarity of being formulated by means of a suitable variational inequality (VI) andits solution is called “equilibrium”. This model becomes a minimum cost model when the cost function is separableor, more general, when the Jacobian of the cost operator is symmetric;in such cases a functional representing the total network utility exists.In fact in these cases we can write the first order optimality conditions which turn out to be a VI.In the other situations (i.e., when global utility functional does not exist),which occur much more often in the real problems, we can study the network by looking for equilibrium solutions instead of minimum points.The Lagrangean approach to the study of the VI allows us to introduce dual variables, associated to the constraints of the feasible set, which may receive interesting interpretations in terms of potentials associated to the arcs and the nodes of the network.This interpretation is an extension and generalization of the classic Bellman conditions. Finally, we deepen the analysis of the networks having capacity constraints.


The notion of treewidth is of considerable interest in relation to NP-hard problems.Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomialtime when treewidth is bounded, even if, for arbitrary graphs, computingthe treewidth is NP-hard.Several papers present heuristics with computational experiments.For many graphs the discrepancy between the heuristic resultsand the best lower bounds is still very large. The aim of this paper is to propose two new methodsfor computing the treewidth of graphs: a heuristic and a metaheuristic.The heuristic returns good results in a short computation time,whereas the metaheuristic (a Tabu search method)returns the best results known to have been obtained so far for all the DIMACS vertex coloring / treewidth benchmarks (a well-known collection of graphs used for both vertex coloring and treewidth problems.) Our results actually improve on the previous best results for treewidth problems in 53% of the cases. Moreover, we identify properties of the triangulation processto optimize the computing time of our method.

In applications such as airport operations, militarysimulations, and medical simulations, conductingsimulations in accurate and realistic settings that are represented byreal video imaging sequences becomes essential. This paper surveys recent work that enablesvisually realistic model constructions and the simulation of syntheticobjects which are inserted in video sequences, and illustrates how synthetic objects canconduct intelligent behavior within a visual augmented reality.

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.

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.

This paper considers an M/M/R/N queue with heterogeneousservers in which customers balk (do not enter) with a constantprobability (1 - b). We develop the maximum likelihoodestimates of the parameters for the M/M/R/N queue with balking andheterogeneous servers. This is a generalization of the M/M/2queue with heterogeneous servers (without balking), and theM/M/2/N queue with balking and heterogeneous servers in theliterature. We also develop the confidence interval formula forthe parameter ρ, the probability of empty system P 0, andthe expected number of customers in the system E[N], of anM/M/R/N queue with balking and heterogeneous servers. The effectsof varying b, N, and R on the confidence intervals of P 0and E[N] are also investigated.

In this paper we study the existence of subharmonic solutions of the Hamiltonian system $$ J\dot x+ u^* \nabla G(t,u(x)) =e(t)$$ where u is a linear map, G is a C 1-function and e is a continuous function.

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.

We consider a G-network with Poisson flow of positive customers.Each positive customer entering the network is characterized bya set of stochastic parameters: customer route, the length of customer route,customer volume and his service length at each route stage aswell. The following node types are considered:Negative customers arriving at each node also form a Poisson flow.A negative customer entering a node with k customers in service, withprobability 1/k chooses one of served positivecustomer as a “target”. Then, if the node is of a type 0the negative customer immediately “kills” (displaces from the network)the target customer, and if the node is of types 1–3the negative customer with given probability depending on parameters of thetarget customer route kills this customer and with complementary probability hequits the network with no service.A product form for the stationary probabilities of underlyingMarkov process is obtained.

The problem of minimizing the maximum edge congestion in a multicastcommunication network generalizes the well-known NP-hard multicommodityflow problem. We give the presently best theoretical approximation results aswell as efficient implementations. In particular we show that for a networkwith m edges and k multicast requests, anr(1 + ε)(rOPT + exp(1)lnm)-approximation can be computed inO(kmε-2 lnklnm) time, where β bounds the time forcomputing an r-approximate minimum Steiner tree. Moreover, we present a newfast heuristic that outperforms the primal-dual approaches with respect toboth running time and objective value.

Cet article introduit une nouvelle transformation des réseaux de Petri généralisés appelée l'abstraction généralisée. C'est une réduction dont nous montrons qu'elle conserve les invariants du réseau de départ et les propriétés structurelles les plus importantes. Une fonction de transformation de marquages nous permet d'introduire l'étude de la conservation des propriétés comportementales.

Les distributions non paramétriques de survie trouvent, de plus en plus, des applications dans desdomaines très variés, à savoir: théorie de fiabilité et analyse de survie, files d'attente,maintenance, gestion de stock, théorie de l'économie, ... L'objet de ce travail estd'utiliser les bornes inférieures et supérieures (en terme de la moyenne) des fonctions defiabilité appartenant aux classes de distribution de type IFR, DFR, NBU et NWU, présentées parSengupta (1994), pour l'évaluation de certaines caractéristiques. Nousutilisons certaines de ces lois pour l'évaluation des bornes du temps moyen d'attente dans la filed'un système d'attente de type GI/GI/1, en actualisant celles trouvées par Stoyan (1983). Comme application à la théorie de renouvellement et de fiabilité, nous utilisonsles propriétés qualitatives des temps de réparation pour borner le temps moyen de vie d'un systèmeà deux éléments réparables.

We consider a Markov decision process for an MX/M/1 queue that iscontrolled by batches of negative customers. More specifically, we deriveconditions that imply threshold-type optimal policies, under either thetotal discounted cost criterion or the average cost criterion. Theperformance analysis of the model when it operates under a giventhreshold-type policy is also studied. We prove a stability condition and acomplete stochastic comparison characterization for models operating underdifferent thresholds. Exact and asymptotic results concerning thecomputation of the stationary distribution of the model are also derived.

A single-server queueing system with a batch Markovian arrivalprocess (BMAP) and MAP-input of disasters causing all customers toleave the system instantaneously is considered. The system has twooperation modes, which depend on the current queue length. Theembedded and arbitrary time stationary queue length distributionhas been derived and the optimal control threshold strategy hasbeen determined.

We consider a multiobjective optimization problem with a feasible setdefined by inequality and equality constraints such that all functionsare, at least, Dini differentiable (in some cases, Hadamard differentiableand sometimes, quasiconvex). Several constraint qualifications are givenin such a way that generalize both the qualifications introduced by Maedaand the classical ones, when the functions are differentiable. Therelationships between them are analyzed. Finally, we give severalKuhn-Tucker type necessary conditions for a point to be Pareto minimumunder the weaker constraint qualifications here proposed.

Dans cet article, nous proposons une nouvelle méthode de purification pour les problèmes de complémentarité linéaire, monotones. Cette méthode associe à chaque itéré de la suite, générée par une méthode de points intérieurs, une base non nécessairement réalisable. Nous montrons que, sous les hypothèses de complémentarité stricte et de non dégénérescence, la suite des bases converge en un nombre fini d'itérations vers une base optimale qui donne une solution exacte du problème. Le procédé adopté sert également à préconditionner l'algorithme de gradient conjugué lors du calcul de la direction de Newton.

In this paper we consider the operational planning problem of physical distribution via a fleet of hired vehicles, for which the travelling cost is solely a function of the sequence of locations visited within all open delivery routes, while vehicle fixed cost is inexistent. The problem is a special class of vehicle routing and is encountered in the literature as the Open Vehicle Routing Problem (OVRP), since vehicles are not required to return to the depot. The goal is to distribute in an optimal way finished goods from a central facility to geographically dispersed customers, which pose daily demand for items produced in the facility and act as sales points for consumers. To solve the problem, we employ an annealing-based method that utilizes a backtracking policy of the threshold value when no acceptances of feasible solutions occur during the search process. Computational results on a set of benchmark problems show that the proposed method consistently outperforms previous algorithms for solving the OVRP. The approach can serve as the means for effective fleet planning in real-life problems.