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.

In this paper, which is an extension of [4],we first show the existence of solutions to a class of Min Sup problems with linked constraints, which satisfy a certain property. Then, we apply our result to a class of weak nonlinear bilevelproblems. Furthermore, for such a class of bilevel problems, wegive a relationship with appropriate d.c. problems concerning theexistence of solutions.

In cutting stock problems, after an optimal (minimal stock usage)cutting plan has been devised, one might want to further reduce theoperational costs by minimizing the number of setups. A setupoperation occurs each time a different cutting pattern begins to beproduced. The related optimization problem is known as the PatternMinimization Problem, and it is particularly hard to solve exactly.In this paper, we present different techniques to strengthen aformulation proposed in the literature. Dual feasible functions areused for the first time to derive valid inequalities from differentconstraints of the model, and from linear combinations of constraints. A new arcflow formulation is also proposed. This formulation is used todefine the branching scheme of our branch-and-price-and-cutalgorithm, and it allows the generation of even stronger cuts bycombining the branching constraints with other constraints of themodel. The computational experiments conducted on instances from theliterature show that our algorithm finds optimalinteger solutions faster than other approaches. A set of computationalresults on random instances is also reported.

We present in this paper a new multiobjective memetic algorithm scheme called MEMOX. In current multiobjective memetic algorithms, the parents used for recombination are randomly selected. We improve this approach by using a dynamic hypergrid which allows to select a parent located in a region of minimal density. The second parent selected is a solution close, in the objective space, to the first parent. A local search is then applied to the offspring. We experiment this scheme with a new multiobjective tabu search called PRTS, which leads to the memetic algorithm MEMOTS. We show on the multidimensional multiobjective knapsack problem that if the number of objectives increase, it is preferable to have a diversified research rather using an advanced local search. We compare the memetic algorithm MEMOTS to other multiobjective memetic algorithms by using different quality indicators and show that the performances of the method are very interesting.

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.

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientationsof an undirected graph. For example, acyclic orientations with certain diameter constraints areclosely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientationswith path constraints, and discuss its use in the solution of the vertex coloring problem andsome versions of the frequency assignment problem. A study of the polytope associated with the formulation is presented, including proofs of which constraints of the formulation are facet-definingand the introduction of new classes of valid inequalities.

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.

Many combinatorial optimization problems can be formulated asthe minimization of a 0–1 quadratic function subject to linear constraints. Inthis paper, we are interested in the exact solution of this problem through atwo-phase general scheme. The first phase consists in reformulating theinitial problem either into a compact mixed integer linear program or into a0–1 quadratic convex program. The second phase simply consists insubmitting the reformulated problem to a standard solver. The efficiency ofthis scheme strongly depends on the quality of the reformulation obtained inphase 1. We show that a good compact linear reformulation can be obtained bysolving a continuous linear relaxation of the initial problem. We also showthat a good quadratic convex reformulation can be obtained by solving asemidefinite relaxation. In both cases, the obtained reformulation profitsfrom the quality of the underlying relaxation. Hence, the proposed scheme getsaround, in a sense, the difficulty to incorporate these costly relaxations ina branch-and-bound algorithm.

An important task of knowledge discovery deals with discovering association rules. This very general model has been widely studied and efficient algorithms have been proposed. But most of the time, only frequent rules are seeked. Here we propose to consider this problem as a multi-objective combinatorial optimization problem in order to be able to also find non frequent but interesting rules. As the search space may be very large, a discussion about different approaches is proposed and a hybrid approach that combines a metaheuristic and an exact operator is presented.

We first describe four recent methods to cluster vertices of anundirected non weighted connected graph. They are all based onvery different principles. The fifth is a combination of classicalideas in optimization applied to graph partitioning. We comparethese methods according to their ability to recover classesinitially introduced in random graphs with more edges within theclasses than between them.

This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.

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.

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three different concepts, involving the facet set of STAB(G), the disjunctive index of QSTAB(G), and the dilation ratio of the two polytopes.
Including only certain types of facets for STAB(G), we obtain graphs that are in some sense close to perfect graphs, for example minimally imperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by Gerke and McDiarmid [12] as the dilation ratio of STAB(G) and QSTAB(G), whereas Aguilera et al. [1] suggest to take the disjunctive index of QSTAB(G) as the imperfection index of G.For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graphclasses [7,12].
Outgoing from a graph-theoretical interpretation of the imperfectionindex, we prove that there exists no upper bound on the imperfection indexfor those graph classes with a known bounded imperfection ratio.Comparing the two invariants on those classes, it seems that theimperfection index measures imperfection much more roughly than theimperfection ratio; we, therefore, discuss possible directions forrefinements.

In this work, we present an introduction to automatic differentiation,its use in optimization software, and some new potential usages. Wefocus on the potential of this technique inoptimization. We do not dive deeply in the intricacies of automaticdifferentiation, but put forward its key ideas. We sketch a survey, asof today, of automatic differentiation software, but warn the readerthat the situation with respect to software evolves rapidly. In thelast part of the paper, we present some potential future usage ofautomatic differentiation, assuming an ideal tool is available, whichwill become true in some unspecified future.

Wireless LAN using IEEE 802.11 networks are now widely deployed athome by residential users or in hot spots by telecommunicationoperators. A hot spot is a place where a set of access points (APs)are located nearby each other and can serve many users. Sinceperturbations can degrade the quality of the signal, a carefulchannel assignment to each AP has to be done. Channel assignment ofAPs at hot spots, and more generally setup configuration andmanagement, is still often done manually. In this paper, we considera modeling that enables optimization of channel assignment withrespect to the dynamic behavior of end-users. We prove our problem'sformulation to correspond to the Minimum Interference FrequencyAssignment Problem, and hence the problem to be NP-hard. We proposeand compare three different tabu search methods to solve theproblem of channel assignment in 802.11 WLAN networks. The firstone, called TabuObj, tackles the problem using directly theobjective function associated with the model. The second one, calledTabuApproxObj, uses a simplified and approximate objectivefunction in order to visit more solutions during the same amount oftime, i.e. to be quicker than TabuObj. The third one, calledTabuLevel, is even more quicker and is based on the followingphilosophy: under time constraints, it could be judicious to explorevery quickly lots of solutions, rather than spending muchcomputation time for the evaluation of each solution, and hence onlyconsidering a few solutions. Those three methods are then comparedbased on time constraints and on the quality of their solutions.