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.

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

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.

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.