In this paper, we study the Steiner 2-edge connected subgraph polytope.We introduce a large class of valid inequalities for this polytope calledthe generalized Steiner F-partition inequalities, that generalizesthe so-called Steiner F-partition inequalities. We show that theseinequalities together with the trivial and the Steiner cutinequalities completely describe the polytope on a class of graphsthat generalizes the wheels. We also describe necessary conditions forthese inequalities to be facet defining, and as a consequence, weobtain that the separation problem over the Steiner 2-edge connectedsubgraph polytope for that class of graphs can be solved in polynomialtime. Moreover, we discuss that polytope in the graphs that decomposeby 3-edge cutsets. And we show that the generalized SteinerF-partition inequalities together with the trivial and the Steinercut inequalities suffice to describe the polytope in a class of graphsthat generalizes the class of Halin graphs when the terminals have aparticular disposition. This generalizes a result of Barahona andMahjoub [4] for Halin graphs. This also yields apolynomial time cutting plane algorithm for the Steiner 2-edgeconnected subgraph problem in that class of graphs.

We study the finite projective planes with linear programmingmodels. We give a complete description of the convex hull of thefinite projective planes of order 2. We give some integer linearprogramming models whose solution are, either a finiteprojective (or affine) plane of order n, or a (n+2)-arc.

We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K 1,3(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K 1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.

The computation of leastcore and prenucleolus is an efficient way ofallocating a common resource among n players. It has, however,the drawback being a linear programming problem with2n - 2 constraints. In this paper we showhow, in the case of convex production games, generate constraints by solving small sizelinear programming problems,with both continuous and integer variables. The approach is extended to games with symmetries (identical players), and to games with partially continuous coalitions. We also study thecomputation of prenucleolus, and display encouraging numerical results.

In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J.Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using aself improving operation in some hard instances. It is interestingto note that this self improving operation does not work for allinstances. Moreover, based on this approach we deduce that theproblem does not admit constant approximation algorithms forconnected planar cubic bipartite graphs.


We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.

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

An algorithm for enumerating all nondominated vectors of multiple objectiveinteger linear programs is presented. The method tests different regionswhere candidates can be found using an auxiliary binary problem for trackingthe regions already explored. An experimental comparision with our previousefforts shows the method has relatively good time performance.

Dans cet article nous proposons une nouvelleméthode d'initialisation du problème de transportclassique. Cette méthode est basée sur le principe d'uneaffectation seulement si nécessaire. Elle donne de bonsrésultats etsouvent la solution optimale.

The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m⋅log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm proposed can be adapted to solve this problem, too. The inverse minimum flow problem considering l ∞ norm is also studied.

This article deals with the vehicle routing problem with timewindows (VRPTW). This problem consists in determining a least-costset of trips to serve customers during specific time windows. Theproposed solution method is a memetic algorithm (MA), a geneticalgorithm hybridised with a local search. Contrary to most paperson the VRPTW, which minimize first the number of vehicles, ourmethod is also able to minimize the total distance travelled. Theresults on 56 classical instances are compared to those of thebest metaheuristics. The efficiency of the MA is similar for theclassical criterion, but it becomes the best algorithm availablefor the total distance, being much faster and improving 20best-known solutions.