In this paper we present a new approach to solve the Minimum Independent Dominating Setproblem in general graphs which is one of the hardest optimization problem. We propose amethod using a clique partition of the graph, partition that can be obtained greedily. Weprovide conditions under which our method has a better complexity than the complexity ofthe previously known algorithms. Based on our theoretical method, we design in the secondpart of this paper an efficient algorithm by including cuts in the search process. We thenexperiment it and show that it is able to solve almost all instances up to 50 vertices inreasonable time and some instances up to several hundreds of vertices. To go further andto treat larger graphs, we analyze a greedy heuristic. We show that it often gives good(sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s.That sort of heuristic is a good approach to get an initial solution for our exact method.We also describe and analyze some of its worst cases.

This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact and approximate resolution when the instance size increases.

We propose here a pricing Model which is an extension of the Cooperative Game concept and which includes a notion of Elastic Demand. We present some existence results as well as some algorithms. We conclude by discussing this model in the context of some Production and Transportation problems.

In this paper, we propose a new class of adaptive trust region methods for unconstrained optimization problems and develop some convergence properties. In the new algorithms, we use the current iterative information to define a suitable initial trust region radius at each iteration. The initial trust region radius is more reasonable in the sense that the trust region model and theobjective function are more consistent at the current iterate. The global convergence, super-linear and quadratic convergence rate are analyzed under some mild conditions. Numericalresults show that some special adaptive trust region methods are available and efficient in practical computation.

We show that the problem of deciding if there is a scheduleof length three for the multiprocessor scheduling problem on identicalmachines and unit execution time tasks in -complete even for bipartitegraphs, i.e. for precedence graphs of depth one. This complexity resultextends a classical result of Lenstra and Rinnoy Kan [5].

We discuss the use of operations research methods for computer-aided design of mechanical transmission systems. We consider how to choose simultaneously transmission ratios and basic design parameters of transmission elements (diameters, widths, modules and tooth number for gears, diameters of shafts). The objectives, by the order of importance, are: to minimize the deviation of the obtained speeds from desired; to maximize the transmission life; to minimize the total mass. To solve this problem, we propose a multi-level decomposition scheme in combination with methods of quadratic and dynamic programming. Some industrial cases are solved. For these cases, the developed software tool improves the design decisions by decreasing total metal consumption of the transmission as much as 7–10% and considerable simplifies the work of the designer.

This paper is devoted to the following version of the single machine preemptive scheduling problem of minimizing the weighted number of late jobs. A processing time, a release date, a due date and a weight of each job are given. Certain jobs are specified to be completed in time, i.e., their due dates are assigned to be deadlines, while the other jobs are allowed to be completed after their due dates. The release/due date intervals are nested, i.e., no two of them overlap (either they have at most one common point or one covers the other). Necessary and sufficient conditions for the completion of all jobs in time are considered, and an O(nlogn) algorithm (where n is the number of jobs) is proposed for solving the problem of minimizing the weighted number of late jobs in case of oppositely ordered processing times and weights.


Nous nous intéressons dans ce travail au problème d'approximation d'une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d'agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées de Boyle-Dykstra.

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

This paper investigates the problem of maximizing the revenue of a telecommunications operator by simultaneously pricing point-to-point services and allocating bandwidth in its network, while facing competition. Customers are distributed into market segments, i.e., groups of customers with a similar preference for the services. This preference is expressed using utility functions, and customers choose between the offers of the operator and of the competition according to their utility. We model the problem as a leader-follower game between the operator and the customers. This kind of problem has classically been modeled as a bilevel program. A market segmentation is usually defined by a discrete distribution function of the total demand for a service; in this case, the problem can be modeled as a combinatorial optimization problem. In this paper, however, we motivate the use of a continuous distribution function and investigate the nonlinear continuous optimization problem obtained in this case. We analyze the mathematical properties of the problem, and in particular we give a necessary and sufficient condition for its convexity. We introduce methods to solve the problem and we provide encouraging numerical results on realistic telecommunications instances of the problem, showing that it can be solved efficiently.

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.

Dans cet article nous caractérisons, par les facettes, l'enveloppe convexe des vecteurs caractéristiques des hyperplans d'un espace projectif fini et d'un espace affine fini.

Given a tree T with n vertices, we show, by using a dynamicprogramming approach, that the problem of finding a 3-coloring ofT respecting local (i.e., associated with p prespecified subsetsof vertices) color bounds can be solved in O(n6p-1 logn)time. We also show that our algorithm can be adapted to the case ofk-colorings for fixed k.

Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0–1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work inthe literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer programming solver. The second one is based on a specialized branch and bound algorithm that reformulates more precisely the problem at every node of search tree. We also propose a heuristic method and we exploit the obtained solution in order to improve the first strategy. We present computational experiments that allow to compare the different approaches.

We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

We present a hybrid approach for the FrequencyAssignment Problem with Polarization. This problem, viewed asMax-CSP, is treated as a sequence of decision problems, CSPlike. The proposed approach combines the Arc-Consistencytechniques with a performed Tabu Search heuristic. The resultingalgorithm gives some high quality solutions and has proved itsrobustness on instances with approximately a thousand variablesand nearly ten thousand constraints.

In this paper, we propose an industrial symbiosis network equilibrium model by usingnonlinear complementarity theory. The industrial symbiosis network consists of industrialproducers, industrial consumers, industrial decomposers and demand markets, which imitatesnatural ecosystem by means of exchanging by-products and recycling useful materialsexacted from wastes. The industrial producers and industrial consumers are assumed to beconcerned with maximization of economic profits as well as minimization of emissions. Wedescribe the optimizing behavior, derive optimality conditions of the variousdecision-makers along with respective economic interpretations and establish the nonlinearcomplementarity model in accordance with the industrial symbiosis network equilibriumconditions. Based on the existence proof of the corresponding nonlinear complementaritymodel under reasonable assumptions, two groups of numerical examples are given toillustrate the rationality as well as the effectiveness of the model.

Recently, [Y.Q. Bai, M. El Ghami and C. Roos,SIAM J. Opt. 15 (2004) 101–128]investigated a new class of kernel functions which differs from theclass of self-regular kernel functions. The class is defined by somesimple conditions on the growth and the barrier behavior of thekernel function. In this paper we generalize theanalysis presented in the above paper for P * (κ) LinearComplementarity Problems (LCPs). The analysis for LCPs deviates significantly from the analysisfor linear optimization. Several new tools and techniques are derived in this paper.

We present a regularization method to approach a solution of the pessimistic formulation of ill-posed bilevel problems. This allows to overcome the difficulty arising from the non uniqueness of the lower level problems solutions and responses. We prove existence of approximated solutions, give convergence result using Hoffman-like assumptions. We end with objective value error estimates.