The multiparametric 0-1-Integer Programming (0-1-IP)problem relative to the objective function is a family of 0-1-IP problemswhich are relatedby havingidentical constraint matrix and right-hand-sidevector. In this paper we present an algorithm to perform a completemultiparametric analysis relative to a generalized min max objectivefunction such that the min sum and min max are particular cases.

Le Problème du Vendeur m-Péripatétique (m-PVP) est défini sur un graphe non orienté G=(V,E) où V = {1,...,n} est l'ensemble des sommets, E = {(i,j) : i,j ∈ V,i < j} est l'ensemble des arêtes et (cij) est une matrice de coûts définie sur E.Le m-PVP consiste à déterminer m cycles hamiltoniens sur G n'ayant aucune arête en commun et dont le coût total est minimal.Cet article décrit sept nouvelles heuristiques pour le m-PVP et les compare à celle qui a été proposée par Krarup en 1975.

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.

This paper studies the machine repairproblem consisting of M operating machines with S sparemachines, and R servers (repairmen) who leave for a vacation ofrandom length when there are no failed machines queuing up forrepair in the repair facility. At the end of the vacation theservers return to the repair facility and operate one of threevacation policies: single vacation, multiple vacation, and hybridsingle/multiple vacation. The Markov process and thematrix-geometric approach are used to develop the steady-stateprobabilities of the number of failed machines in the system aswell as the performance measures. A cost model is developed toobtain the optimal values of the number of spares and the numberof servers while maintaining a minimum specified level of systemavailability. Some numerical experiments are performed and someconclusions are drawn.

A reformulation of a mathematical program is a formulation whichshares some properties with, but is in some sense better than, theoriginal program. Reformulations are important with respect to thechoice and efficiency of the solution algorithms; furthermore, it isdesirable that reformulations can be carried outautomatically. Reformulation techniques are widespread in mathematicalprogramming but interestingly they have never been studied under aunified framework. This paper attempts to move some steps in thisdirection. We define a framework for storing and manipulatingmathematical programming formulations and give several fundamentaldefinitions categorizing useful reformulations in essentially fourtypes (opt-reformulations, narrowings, relaxations andapproximations). We establish some theoretical results and givereformulation examples for each type.

Nous nous intéressons dans cet article au problème dedécoupeguillotine en deux dimensions noté 2BP/O/G. Il s'agit dedécouper un certain nombre de pièces rectangulaires dans unensemble de plaques de matière première, elles même rectangulaireset identiques. Celles-ci sont disponibles en quantité illimitée.L'objectif est de minimiser le nombre de plaques utilisées poursatisfaire la demande, en appliquant une succession de coupes,dites guillotines, allant de bout en bout. Nous proposons uneapproche de résolution combinant l'optimisation par colonies defourmis (ACO) et l'heuristique SHF-FF de Ben Messaoud et al. [2] pour résoudre ce problème NP-difficile.


Matthews and Sumner have proved in [10] that if G is a 2-connectedclaw-free graph of order n such that δ(G) ≥ (n-2)/3, then G isHamiltonian. We say that a graph is almost claw-free if for every vertexv of G, 〈N(v)〉 is 2-dominated and the set A of centers of claws of G isan independent set. Broersma et al. [5] have proved that if G isa 2-connected almost claw-free graph of order n such that n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these resultsby considering the graphs satisfying the following property: for everyvertex v ∈ A, there exist exactly two vertices x and y of V\A such that N(v) ⊆ N[x] ∪ N[y]. We extend some other knownresults on claw-free graphs to this new class of graphs.