In this paper, we present anew mathematical programming formulation for the Euclidean SteinerTree Problem (ESTP) in ℜ. We relax the integralityconstrains on this formulation and transform the resultingrelaxation, which is convex, but not everywhere differentiable,into a standard convex programming problem in conic form. Weconsider then an efficient computation of an ϵ-optimalsolution for this latter problem using interior-point algorithm.

In this note, we present a slight modification of an algorithm for thestrict feasibility problem. This modification reducesthe number of iterations.

A branch-and-bound method for solving the min cut with size constraint problemis presented. At each node of the branch-and-bound tree the feasible set isapproximated by an ellipsoid and a lower bound is computed by minimizing thequadratic objective function over this ellipsoid. An upper bound is alsoobtained by a Tabu search method. Numerical results will be presented.

We present, in this article, a hybrid approach forsolvingthe 0–1 multidimensional knapsack problem (MKP). This approach combineslinearprogramming and Tabu search.The resulting algorithm improves on the best result on many well-knownhard benchmarks.

In this paper we study the main properties of the strongBerge equilibrium, then we prove a theorem of its existence based on the KyFan inequality and finally, we provide an algorithm for its determination.