Consultation des rapports

216

Equitable total coloring of cubic graphs is NP-complete

Simone Dantas,  Celina M. H. De Figueiredo,  Giuseppe Mazzuoccolo,  Myriam Preissman,  Vinicius F. Dos Santos,  Diana Sasaki

A total coloring is equitable if the number of elements colored with each color differs by
at most one, and the least integer for which a graph has such a coloring is called its equitable
total chromatic number. It is conjectured that the equitable total chromatic number of a
graph is at most Δ + 2, and this has already been proved for cubic graphs. Therefore, the
equitable total chromatic number of a cubic graph is either 4 or 5. In this work we prove
that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.
Furthermore, we establish for one infinite family of Type 1 cubic graphs that they all
have equitable total chromatic number 4.

Keywords: total coloring, equitable total coloring, cubic graphs

215

Integer round-up property for the chromatic number of some h-perfect graphs

Yohann Benchetrit

A graph is h-perfect if its stable set polytope can be completely described by non-negativity, clique and odd-hole constraints. It is t-perfect if it furthermore has no clique of size 4.

For every graph $G$ and every $cinmathbb{Z}_+^{V(G)}$, the weighted chromatic number of $(G,c)$ is the minimum cardinality of a multi-set $mathcal{F}$ of stable sets of $G$ such that every $vin V(G)$ belongs to at least $c_v$ members of $mathcal{F}$.

We prove that emph{every h-perfect line-graph and every t-perfect claw-free graph $G$ has the integer round-up property for the chromatic number} : for every non-negative integer weight $c$ on the vertices of $G$, the weighted chromatic number of $(G,c)$ can be obtained by rounding up its fractional relaxation. In other words, the stable set polytope of $G$ has the integer decomposition property.

Another occurrence of this property was recently obtained by Eisenbrand and Niemeier for fuzzy circular interval graphs (extending previous results of Niessen, Kind and Gijswijt). These graphs form another proper subclass of claw-free graphs.

Our results imply the emph{existence of a polynomial-time algorithm which computes the weighted chromatic number of t-perfect claw-free graphs and h-perfect line-graphs}. They also yield a new case of a conjecture of Goldberg and Seymour on edge-colorings.

Finally, we settle a problem raised by Shepherd by showing an example of emph{a 3-colorable t-perfect graph which does not have the integer round-up property}.

214

A possible connection between girth and total chromatic parameters in cubic graphs

Simone Dantas,  Celina M. H. De Figueiredo,  Giuseppe Mazzuoccolo,  Myriam Preissmann,  Vinicius F. Dos Santos,  Diana Sasaki

A cubic graph is said to be Type 1 if it has total chromatic number equal to 4 and
otherwise it is said to be Type 2. We consider the following question about total colorings
of cubic graphs of large girth: Does there exist a Type 2 cubic graph of girth greater
than 4? Moreover, we formulate a new question about a possible connection between girth
and equitable total colorings: Does there exist a Type 1 cubic graph of girth greater than 4
with equitable total chromatic number 5?
We exhibit infinite families of cubic graphs that indicate that possibly both questions
would have a negative answer. Notice that a negative answer for the first question would
provide a result much stronger than a recent theorem about fractional total colorings of
cubic graphs. In particular, we prove that almost all generalized Petersen graphs are Type 1.
Furthermore, we present a sufficient condition for a cubic graph to be Type 2, contributing
to the search for an answer to the first question.

213

A comparison of inventory policies coupled with a flexible sales and operations planning under long procurement lead times

Lâm Laurent Lim,  Gülgün Alpan,  Bernard Penz

A new challenge for industries is to manage efficiently sales and operations in an uncertain and global environment. The sales and operations planning (S&OP) aims to improve the trade-off between production costs and customer satisfaction. For products with long procurement lead times, new flexibility parameters can be used in the S&OP to improve the supply chain agility and to satisfy efficiently customer demands. In this paper, we consider several inventory policies integrated within a flexible S&OP model. The problem is formulated as a stochastic multi-objective optimization model solved by a simulation-optimization approach. Based on the case study of the automobile manufacturer, Renault, we present a numerical comparative study of the different strategies in terms of system performance. We also provide managerial insights that are particularly relevant to improve the S&OP and inventory management for companies that face uncertain demand, impatient customers and distant sourcing.

212

A simulation-optimization approach for managing the sales and operations planning in the automotive industry

Lâm Laurent Lim,  Gülgün Alpan,  Bernard Penz

Due to the increasing globalization and the distant sourcing, reconciling industrial constraints and sales requirements becomes very challenging for industries facing an uncertain environment and demanding customers. The sales and operations planning (S&OP) is crucial for efficiently balancing production capacities with the volatile market demand. In this article, we propose an original S&OP model in order to improve the trade-off between the supply chain costs and the customer satisfaction. The problem is formulated as a multi-objective optimization model with epsilon-constraints and is solved by a simulation-optimization approach. Two classes of policies for managing the parts procurement and the flexibility offered to the sales function are presented. The model and the proposed solution are illustrated with the case study of Renault, a French global automobile manufacturer. Several policies and optimization algorithms are compared in terms of system performance and computation time. Managerial insights are derived based on these results.

211

Issues in the complementary use of simulation and optimization modeling

Anne-Laure Ladier,  Allen G. Greenwood,  Gülgün Alpan,  Halston Hales

Simulation models and discrete optimization models are oftentimes used together in a variety of ways. In this paper, we discuss the issues that modelers must address in cases where simulation models are used to test a discrete mathematical programming optimization model’s performance in a stochastic environment. The issues arise during validation of simulation models, when checking agreement between deterministic optimization results and simulation models operating under deterministic conditions. In our case, the issues are derived from validating simulation models that are used to test the performance of scheduling and resource allocation models (integer and mixed-integer programming optimization models) under various types of uncertainty. While the concerns we describe are from our work in the logistics domain (cross-docking operations), they are relevant to a wide variety of problem domains. In addition to describing the issues, we offer suggestions on how modelers might address the concerns.

210

Reconciling sales and operations management with distant suppliers in the automotive industry: a simulation approach

Lâm Laurent Lim,  Gülgün Alpan,  Bernard Penz

A challenge for car manufacturers is to adjust rapidly and efficiently the production capacities with a volatile market demand and despite distant suppliers. In this paper, we consider a sales and operations planning problem based on the actual situation of Renault, a French global automobile manufacturer. The issue is to find the best trade-off between sales requirements and industrial constraints while limiting inventories, emergency supplies and keeping delivery lead times reasonable for customers. A new planning method based on flexibility rates is presented. The flexibility rates are defined to limit orders of a given type of vehicles, during a certain period. A simulation model is introduced and captures the dynamics of the sales and operations management. A numerical study has been performed by using industrial data. Results highlight factors that improve system performances and several policies are compared. This research has also relevance for other industries that face long procurement lead times in an uncertain environment.

209

Additions to Lawler’s min-max cost algorithm: Optimality conditions and uncertainty

Nadia Brauner,  Gerd Finke,  Yakov Shafransky,  Dzmitry Sledneu

The well-known O(n2) min-max cost algorithm of Lawler [2] was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. The first one concerns necessary and sufficient conditions for the sequence optimality when all the cost functions are strictly increasing. The second result concerns the scheduling on a single machine under both uncertainty of some job’s parameters and precedence constraints. In the latter problem, each job has an asso- ciated non-decreasing cost function of a special (decomposable) form. The cost function for each job depends on the job completion time and on an additional parameter value. The aim is to find a schedule for processing the jobs that is feasible with respect to the given prece- dence constraints and that minimizes the maximum cost over all the jobs. The class of the functions under consideration includes known functions such as the maximum lateness and the maximum delivery time. For the problem under uncertainty (where for each job, we know only an interval for possible values of the additional parameter), we derive an O(n2) algorithm for constructing a schedule that minimizes the maximal regret criterion. To obtain this schedule, we use Lawler’s algorithm as a part of our technique.

208

Semi-Online Bin Stretching with Bunch Techniques

We are given a sequence of items that can be packed into $m$ unit size bins and the goal is to assign these items online to m bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 improving the best known algorithm by Kellerer and Kotov with a stretching factor 11/7. Our algorithms has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose.

207

Complements of nearly perfect graphs

András Gyárfás,  Zhentao Li,  Raphael Machado,  András Sebő,  Nicolas Trotignon

A class of graphs closed under taking induced subgraphs is $\chi$-bounded if there exists a function $f$ such that for all graphs $G$ in the class, $\chi(G) \leq f(\omega(G))$.
We consider the following question initially studied in [A.~Gy{\’a}rf{\’a}s,\newblock Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413–441, 1987]. For a $\chi$-bounded class $\cal C$, is the class $\overline{C}$ $\chi$-bounded (where $\overline{\cal C}$ is the class of graphs formed by the complements of graphs from $\cal C$)?

We show that if $\cal C$ is $\chi$-bounded by the constant function $f(x)=3$, then $\overline{\cal C}$ is $\chi$-bounded by $g(x)=\lfloor\frac{8}{5}x\rfloor$ and this is best possible.
We show that for every constant $c>0$, if $\cal C$ is $\chi$-bounded by a function $f$ such that $f(x)=x$ for $x \geq c$, then $\overline{\cal C}$ is $\chi$-bounded. For every $j$, we construct a class of graphs $\chi$-bounded by $f(x)=x+x/\log^j(x)$ whose complement is not $\chi$-bounded.

206

Stability Contract in the Forest Products Supply Chain: Case Study for a Quebec Region

Bertrand Hellion,  Sophie D’Amours,  Nadia Lehoux,  Fabien Mangione,  Bernard Penz

In this paper an industrial case including a papermill and its three suppliers (sawmills) is studied.
Sawmills produce lumber and chips from wood, and the paper mill needs these chips to make paper.
These sawmills assign a lower priority to the chips market even though the paper mill is their main customer.
The focus of the research is therefore on securing the paper mill supply by creating beneficial contracts for both stakeholders.
Industrial constraints are taken into account, leading to separate contract designs.
Contracts are then tested on various instances and compared to a centralized model that optimizes the total profit of the supply chain.
Results show that the decentralized profit with separate contracts is $99.3\%$ the centralized profit, for a fixed demand variance.
Difference between centralized and decentralized profit slightly increases with the variance, to reach $3\%$ for a variance of $50\%$.

205

Single-machine production and maintenance: a unified approach

Gerd Finke,  Marie-Laure Espinouse,  Ahmed Gara-Ali,  Vincent Jost,  Julien Moncel

We are presenting a general unifying framework for production-maintenance systems on a single machine. Several performance criteria are included as well as most of the maintenance systems that are proposed in the literature. No particular analytical functions are required and no new algorithms have to be developed. One may simply utilize standard software for min-cost network flow problems.

204

A polynomial time algorithm for the single-item lot sizing problem with capacities, minimum order quantities and dynamic time windows

Bertrand Hellion,  Fabien Mangione,  Bernard Penz

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows.
This problem models a lot sizing where the production lots are constrained in amount and frequency.
In this problem, a demand must be satisfied at each period t over a planning horizon of T periods.
This demand can be satisfied from the stock or by a production at the same period.
When a production is made at period $t$, the produced quantity must be greater than a minimum order quantity (L) and lower than the production capacity (U).
The frequency constraints on the production lots are modeled by dynamic time windows.
Between two consecutive production lots, there is at least Q periods and at most R periods.
An optimal algorithms in O(T^9) is given.
The complexity of the algorithm is reduced to O(T^7) when all the demands are strictly positive.

203

Construction of snarks with total chromatic number 5

Gunnar Brinkmann,  Myriam Preissmann,  Diana Sasaki

A k-total-coloring of G is an assignment of k colors to the edges
and vertices of G, so that adjacent or incident elements have different
colors. The total chromatic number of G, denoted by T (G), is the
least k for which G has a k-total-coloring. It was proved by Rosenfeld
that the total chromatic number of a cubic graph is either 4 or 5.
Cubic graphs with T = 4 are said to be Type 1, and cubic graphs
with T = 5 are said to be Type 2.
Snarks are cyclically 4-edge-connected cubic graphs that do not
allow a 3-edge-coloring. In 2003, Cavicchioli et al. asked for a Type 2
snark with girth at least 5, but as neither Type 2 snarks nor Type 2
cubic graphs with girth at least 5 are known, this is taking two steps
at once and the two requirements of being a snark and having girth at
least 5 should better be treated independently. In this paper we will
show that the property of being a snark can be combined with being
Type 2. We will give a construction that gives Type 2 snarks for each
even vertex number n 40.
We will also give the result of a computer search showing that
among all Type 2 cubic graphs on up to 32 vertices, all but three
contain an induced chordless cycle of length 4. These three exceptions
contain triangles. The question of the existence of a Type 2 cubic
graph with girth at least 5 remains open.

202

Fast recognition of doubled graphs

Frédéric Maffray

Double split graphs form one of the five basic classes in the proof of
the strong perfect graph theorem by Chudnovsky, Robertson, Seymour and
Thomas [The strong perfect graph theorem, Annals of Mathematics
164 (2006) 51–229]. A doubled graph is any induced subgraph of a
double split graph. Alexeev, Fradkin and Kim [Forbidden induced
subgraphs of double-split graphs, SIAM J. Discrete Math. 26
(2012) 1–14] established that the class of doubled graphs is
characterized by a list of 44 forbidden induced graphs of order at
most 9. It follows that deciding if a graph G is a doubled graph
can be done in time O(|V(G)|^9). We show here that this can be done
in time O(|V(G)|+|E(G)|) by analyzing the degree structure of the
graph.

201

Stability contracts between supplier and retailer: a new lot sizing model

Bertrand Hellion,  Fabien Mangione,  Bernard Penz

This work explores the relationship between decision makers in a company and
their suppliers, using stability contracts. This relationship can be modeled as a capac-itated multi-machine lot sizing problem with minimum order quantity and dynamic
time windows, where orders are represented by production levels. Both the amount
and the frequency of orders are constrained, the first by upper and lower bounding
and the second by dynamic time windows. A mathematical model is provided and
an experimental analysis is conducted. Conclusions are given leading to insight for
decision makers and contract designers.

200

On the excessive [m]-index of a tree

Giuseppe Mazzuoccolo

The excessive [m]-index of a graph G is the minimum number of matchings of size m needed to cover the edge-set of G. We call a graph G [m]-coverable if its excessive [m]-index is finite. Obviously the excessive [1]-index is |E(G)| for all graphs and it is an easy task the computation of the excessive [2]-index for a [2]-coverable graph. The case m=3 is completely solved by Cariolaro and Fu in 2009. In this paper we prove a general formula to compute the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.

199

The chromatic number of {P5, K4}-free graphs

Louis Esperet,  Laetitia Lemoine,  Frédéric Maffray,  Grégory Morel

Gyárfás conjectured that for any tree T every T-free graph G
with maximum clique size omega(G) is f_T(omega(G))-colorable,
for some function f_T that depends only on T and omega(G).
Moreover, he proved the conjecture when T is the path Pk on k
vertices. In the case of P5, the best values or bounds known so
far are f_P5(2)=3 and f_P5(q) ? 3^{q-1}. We prove here
that f_P5(3)=5.

198

Shorter Tours by Nicer Ears : 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

András Sebő,  Jens Vygen

We prove new results for approximating the graphic TSP and some related problems.
We obtain polynomial-time algorithms with improved approximation guarantees.

For the graphic TSP itself, we improve the approximation ratio
to $7/5$.
For a generalization, the connected-$T$-join problem, we
obtain the first nontrivial approximation algorithm, with ratio $3/2$.
This contains the graphic $s$-$t$-path-TSP as a special case.
Our improved approximation guarantee for finding a smallest $2$-edge-connected spanning subgraph is $4/3$.

The key new ingredient of all our algorithms is a special kind of ear-decomposition
optimized using forest representations of hypergraphs.
The same methods also provide the lower bounds (arising from LP relaxations)
that we use to deduce the approximation ratios.

medskip
oindent

oindent{{f keywords:} traveling salesman problem, graphic TSP, $2$-edge-connected subgraph,
$T$-join, ear-decomposition, matroid intersection, forest representation, matching.

197

Packing of Rigid Spanning Subgraphs and Spanning Trees

Joseph Cheriyan,  Zoltán Szigeti,  Olivier Durand de Gevigney

We prove that every (6k + 2l,2k)-connected simple graph contains k rigid and l connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jordán [4] and a theorem of Jordán [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lovász and Yemini [9] saying that every 6-connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every 8-connected graph packs a spanning tree and a 2-connected spanning subgraph; (2) every 14-connected graph has a 2-connected orientation.

196

The hunting of a snark with total chromatic number 5

Diana Sasaki,  Simone Dantas,  Celina De Figueiredo,  Myriam Preissmann

A snark is a cyclically-4-edge-connected cubic graph with chromatic index 4. In 1880, Tait proved that the Four-Color Conjecture is equivalent to the statement that every planar bridgeless cubic graph has chromatic index 3. The search for counter-examples to the Four- Color Conjecture motivated the definition of the snarks.
A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent or incident elements have different colors. The total chromatic number of G is the least k for which G has a k-total-coloring. It is known that the total chromatic number of a cubic graph is either 4 or 5. However, the problem of determining the total chromatic number of a graph is NP-hard even for cubic bipartite graphs.
In 2003, Cavicchioli et al. reported that their extensive computer study of snarks shows that all square-free snarks with less than 30 vertices have total chromatic number 4, and asked for the smallest order of a square-free snark with total chromatic number 5.
In this paper we prove that the total chromatic number of both Blanusa families and an infinite snark family (including the Loupekhine and Goldberg snarks) is 4. Relaxing any of the conditions of cyclic-edge-connectivity and chromatic index, we exhibit cubic graphs with total chromatic number 5.
Keywords: snark, total coloring, edge coloring

195

Securing production resources in decentralized supply chain planning

Maxime Ogier,  Van-Dat Cung,  Julien Boissière

Supply chain optimization is a very complex task when taking into account its inherently decentralized aspect and sustainable development considerations. In order to provide a sustainable supply chain model faithful to reality, this paper presents a two actors supply chain model with a manufacturer and a 3PL provider. Centralized and decentralized planning at tactical level, with lot-sizing models, presented by Jung et al. (2008) is studied. This model is extended by including rolling planning horizon, and demand forecast errors, to take into account difficulties of supply chain actors to evaluate future demands. A preliminary experimental study highlights the good economic performance of the decentralized planning and the consequences of demand uncertainty on supply chain total cost. Then, we point out the poor production resource management with rolling horizon planning. Because of social consequences that may result, a new constraint is integrated in the supply chain model : securing production resources. This results in the impossibility to modify the planning on the coming periods. The economic impact of the integration of this social criteria is studied. Results are presented based on deterministic or stochastic demands, and with different rolling horizon length. It points out that securing production resource is not very expensive when planning on a small rolling horizon or with deterministic demands. Various future extensions of this model are also discussed.

194

Stochastic Scheduling with Impatience to the Beginning of Service

Alexandre Salch,  Jean-Philippe Gayon,  Pierre Lemaire

In this paper we discuss a stochastic scheduling problem with impatience to the beginning of service. The impatience of a job can be seen as a due date and a job is considered to be on time if it begins to be processed before its due-date. Processing times and due dates are random variables. Jobs are processed on a single machine with the objective to minimize the expected weighted number of tardy jobs in the class of static list scheduling policies. We derive optimal schedules when processing times and due dates follow different probability distributions. We also study the relation between the problem with impatience to the beginning of service and the problem with impatience to the end of service. Finally, we provide some additional results for the problem with impatience to the end of service.

193

A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs

Bertrand Hellion,  Bernard Penz,  Fabien Mangione

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSP-MOQ). In this problem, a demand must be satis ed at each period t over a planning horizon of T periods. This demand can be satis ed from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T5) is proposed and it is computationally tested on various instances.

192

b-coloring of some bipartite graphs

Mostafa Blidia,  Noureddine Ikhlef Eschouf,  Frédéric Maffray

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number b(G) of a graph G is the largest integer k such that G admits a b-coloring with k colors. We show that every graph of order n, different from a clique, satisfies b(G) ? [n + w(G) -1]/2, where w(G) is the maximum clique size in G, and we give a characterization of bipartite graphs that achieve equality in this bound. Also we show that every graph G satisfies b(G) – chi(G) ? [n/2] – 2, and we deduce a characterization of graphs that achieve this bound. In [2] it was shown that if G is a connected graph of order n ? 5, then for every vertex v of G we have b(G-v) ? b(G) + [n/2] – 2. We confirm this result for an arbitrary graph of order n ? 4 and we conjecture that this bound is attained if and only if G = C4, P4 or 2P2.

191

On 3-colorable P5-free graphs

Frédéric Maffray,  Grégory Morel

We consider the class of P5-free 3-colorable graphs. We give a complete description of the structure of the graphs in that class. We derive a linear time algorithm that tests membership in the class.
The algorithm also finds a maximum weight stable set in linear time.

190

Schedulling of washing operations in a hospital sterilization service for minimizing the mean predisinfection excess time of medical devices

Onur Ozturk,  Maria Di Mascolo,  Marie-Laure Espinouse,  Alexia Gouin

After use in operating blocs, medical devices (MD) are sent to the sterilization service. The sterilization process is composed of various steps. In the washing step, after predisinfection, different sets of MD, used for different surgical operations, may be washed together without exceeding washer capacity. It is generally not allowed to split MD sets among several washers. In this paper, we model the washing step as a batch scheduling problem, where MD sets are denoted as jobs having different sizes and different release dates, but equal processing times for the washing. The washing steps of sterilization services generally constitute a bottleneck for the entire sterilization process and long pre-disinfection times may corrode MD. Hence, the decisions for batching the MD sets and launching washing cycles are crucial in order to minimize the waiting time of MD in the washing step. First, we provide a MILP model for the minimization of mean pre-disinfection excess time and then a ?-constraint model for the minimization of a second criterion which is the number of washing cycles. Afterwards, two heuristics are developed and experimented on the instances inspired from a real case.

189

Generic algorithms for some decision problems on fasciagraphs and rotagraphs

Marwane Bouznif,  Julien Moncel,  Myriam Preissmann

A fasciagraph consists in a sequence of copies of the same graph, each copy being linked to the next one according to a regular scheme. More precisely a fasciagraph is characterized by an integer $n$ (the number of copies or fibers) and a mixed graph $M$. In a rotagraph, the last copy is also linked to the first one. In the literature, similar methods were used to address various problems on rotagraphs and fasciagraphs. The goal of our work is to define a class of decision problems for which this kind of methods works. For this purpose, we introduce the notion of pseudo-$d$-local $q$-properties of fasciagraphs and rotagraphs. For a mixed graph $M$ and a pseudo-$d$-local $q$-property $mathcal{P}$, we propose a generic algorithm for rotagraphs (resp. fasciagraphs) that computes in constant time a closed formula as a boolean function $au$ (resp. $varphi$) on $mathbb{N}$. For all $n in mathbb{N}$ $au(n)=1$ (resp. $varphi(n)=1$) if and only if the rotagraph (resp. fasciagraph) of length $n$ based on $M$ satisfies $mathcal{P}$.

188

MINIMIZING THE TOTAL DURATION OF THE WASHING STEP IN A HOSPITAL STERILIZATION SERVICE

Onur Ozturk,  Marie-Laure Espinouse,  Maria Di Mascolo,  Alexia Gouin

In this paper, we study the problem of minimizing the total duration of the washing operations in hospital sterilization services. After use in operating blocs, reusable medical devices (RMD) are sent to the sterilization service, which is composed of various steps. In the washing step, different sets of RMD, used for different surgeries, may be washed together without exceeding washer capacity. It is generally not allowed to split RMD sets among several washers.
We consider a batch scheduling problem where RMD sets are denoted as jobs having different sizes and different release dates, but equal processing times for the washing. We give optimal algorithms for a special case of the problem where job sizes form a strongly divisible sequence and for another case when job splitting is allowed, respectively. Afterwards, a mixed integer linear programming model is developed for our problem, and an approximation algorithm with worst case ratio of 2 is presented.

187

On disjoint paths in acyclic planar graphs

Guyslain Naves

We give an algorithm with complexity $O(f (R)^{k^2} k^3 n)$ for the integer multiflow problem on instances $(G, H, r, c)$ with $G$ an acyclic planar di-graph and $r + c$ Eulerian. Here, $f$ is a polynomial function, $n = |V (G)|$, $k = |E(H)|$ and $R$ is the maximum request $max_{h∈E(H)} r(h)$. When $k$ is fixed, this gives a polynomial algorithm for the arc-disjoint paths problem under the same hypothesis.

186

Toward an Optimal Scan Insertion at the Register Transfer Level

Lilia Zaourar,  Yann Kieffer,  Nadia Brauner,  Chouki Aktouf

This work shows improvements towards effective consideration of scan pre-synthesis. A new algorithm is proposed to optimally decide about scan stitching at RTL. Algorithm efficiency is proven through an industrial RTL-to-GDS design flow and typical design benchmarks.

185

A superlinear bound on the number of perfect matchings in cubic bridgeless graphs

Louis Esperet,  Frantisek Kardos,  Daniel Kral

Lovasz and Plummer conjectured in the 1970’s that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear bound in the general case.

184

The chromatic gap and its extremes

András Gyárfás,  András Sebő,  Nicolas Trotignon

The chromatic gap is the difference between the chromatic number and the clique number of a graph. Here we investigate gap(n), the maximum chromatic gap over graphs on n vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for gap(n) in terms of Ramsey numbers. For our purposes it is more convenient to work with the covering gap, the difference between the clique cover number and stability number of a graph and this is what we call the gap of a graph. Then gap(n) can be equivalently defined (by switching from a graph to its complement), as the maximum gap over graphs of n vertices. Notice that the well-studied family of perfect graphs are the graphs whose induced subgraphs have gap zero. Our study is a first step towards better understanding of graphs whose induced subgraphs have gap at most t. The maximum of the (covering) gap and the chromatic gap running on all induced subgraphs will be called perfectness gap.

Using alpha(G) for the cardinality of a largest stable (independent) set of a graph G, we define alpha(n) = min alpha(G) where the minimum is taken over triangle-free graphs on n vertices. It is easy to observe that alpha(n) is essentially an inverse Ramsey function, defined by the relation R(3, alpha(n)) ≤ n < R(3, alpha(n)+1).
Our main result is that gap(n) = ceiling of n/2 – alpha(n), possibly with the exception of small intervals (of length at most 15) around the Ramsey numbers R(3,m), where the error is at most 3.

The central notions in our investigations are the gap-critical and the gap-extremal graphs. A graph G is gap-critical if for every proper induced subgraph H of G, gap(H) < gap(G) and gap-extremal if it is gap-critical with as few vertices as possible (among gap-critical graphs of the same gap). The strong perfect graph theorem, solving a long standing conjecture of Berge that stimulated a broad area of research, states that gap-critical graphs with gap 1 are the holes (chordless odd cycles of length at least five) and antiholes (complements of holes). The next step, the complete description of gap-critical graphs with gap 2 would probably be a very difficult task. As a very first step, we prove that there is a unique 2-extremal graph, 2C5, the union of two disjoint (chordless) cycles of length five.

In general, for t ≥ 0, we denote by s(t) the smallest order of a graph with gap t and we call a graph is t-extremal if it has gap t and order s(t). It is tempting to conjecture that s(t) = 5t with equality for the graph tC5. However, for t ≥ 3 the graph tC5 has gap t but it is not gap-extremal (although gap-critical). We shall prove that s(3) = 13, s(4) = 17 and s(5) is 20 or 21. Somewhat surprisingly, after the uncertain values s(6) in {23, 24, 25}, s(7) in {26, 27, 28}, s(8) in {29, 30 , 31}, s(9) in {32, 33} we can show that s(10) = 35. On the other hand we can easily show that s(t) is asymptotically equal to 2t, that is, gap(n) is asymptotic to n/2. According to our main result the gap is actually equal to ceiling of n/2 – alpha(n), unless n is in an interval [R, R + 14] where R is a Ramsey number, and if this exception occurs the gap may be larger than this value by only a small constant (at most 3).

The definition of s(t) does not change if we replace (covering) gap by chromatic gap, so it can in fact be defined with the perfectness gap as well: it is the smallest order of a graph with perfectness gap equal to t.
Our study shows that triangle-free Ramsey graphs have high matchability and connectivity properties, therewith providing some new properties of the Ramsey-graphs themselves, and leading possibly to new bounds on Ramsey-numbers.

183

Disruption management for commercial aviation, a mixed integer programming approach

Julien Darlay,  Louis-Philippe Kronek,  Susann Schrenk,  Lilia Zaourar

In this paper we describe our approach to the airline disruption problem which was the topic of the ROADEF’09 challenge. The aim of the challenge was to re-assign aircrafts and passengers simultaneously in case of disruption, w.r.t. maintenance constraints. We decompose the problem into two main steps: re-assignment of aircrafts on flights, and re-accommodation of passengers on operated flights. Both steps take profit of the initial optimized plan, such as passengers are already involved in aircraft re-assignment. These steps are simply modelled as multicommodity network flows with side constraints and solved using a MIP-solver. We report the numerical results on the instances provided during that challenge. These results have been quite improved since the end of the challenge with just a little modification in our program.

182

Dense and sparse graph partition

Julien Darlay,  Nadia Brauner,  Julien Moncel

In a graph G = (V, E), the density is the ratio between the number of edges |E| and the number of vertices |V|. This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion, the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NP-hard by giving a reduction from graph-k-colorability. Additionally, we give a polynomial time algorithm for the special case of trees.

181

Polynomial time algorithms for makespan minimization on one machine with forbidden start and completion times

We consider independent jobs to sequence on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed neither to start not to complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive a quite fast algorithm to find such a schedule, based on an hybridization between list algorithm and local exchange. We then improve our approach to propose a strongly polynomial time algorithm under a High Multiplicity encoding. As a corollary minimizing the makespan for a constant number of forbidden instants is polynomial.

180

Comparaison de différentes formulations de conception de réseaux pour un problème de transport de fret avec gestion de véhicules.

Susann Schrenk,  Teodor Gabriel Crainic,  Cung Van-Dat,  Gerd Finke

Dans cet article, on s’intéresse à l’étude de la maximisation du profit d’un transporteur de fret. Ce problème intègre la gestion des flux de véhicules simultanément à celle des flux de marchandises.

Nous proposons deux modèles linéaires en nombres entiers, l’un fondé sur des variables arcs pour les véhicules, l’autre sur des variables chemins pour les véhicules, les deux avec des variables arcs pour les marchandises. La comparaison expérimentale de ces deux modèles indique que la formulation « chemin » a une bien meilleure relaxation linéaire que la formulation « arc », réputée faible. Cette dominance est également prouvée par une comparaison théorique des deux modèles.

179

Identical coupled task scheduling: polynomial complexity of the cyclic case

Vassilissa Lehoux-Lebacque,  Nadia Brauner,  Gerd Finke

178

Single Machine Scheduling with Small Operator-Non-Availability Periods

C. Rapine,  N. Brauner,  G. Finke,  V. Lebacque

Through an industrial application, we were confronted with the planning of experiments where human intervention of a chemists is required to handle the starting and termination.
This gives rise to a new type of scheduling problems, namely problems of finding schedules with time periods when the tasks can neither start nor finish. We consider in this paper the natural case of small periods where the duration of the periods is smaller than any processing time. This assumption corresponds to experiments lasting several days whereas the operator unavailability periods are the week-ends. These problems are analyzed on a single machine with the makespan as criterion.
We first prove that, contrary to the case of machine unavailability, the problem with one small operator non-availability period can be solved in polynomial time. We then derive approximation and inapproximability results for the general case of k small unavailability periods. We finally focus on the practical case of periodic and equal small unavailability periods. We prove that this problem is not in FPTAS for more than 3 periods and we derive an FPTAS for the two-period case.

177

The hardness of routing two pairs on one face

Guyslain Naves

We prove the NP-completeness of the integer multiflow problem in planar graphs, with the following restrictions: there are only two edges of demand, both lying on the infinite face of the routing graph. It solves a question from Müller. We also give a directed version with only two terminals, and a directed acyclic version, both we only two arcs of demand.

176

Ramsey-type results for Gallai colorings

András Gyárfás,  Gábor Sárközi,  András Sebő,  Stanley Selkow

A Gallai-coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai-colorings occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper) or information theory. Gallai-colorings extend 2-colorings of the edges of complete graphs. They actually turn out to be close to 2-colorings – without being trivial extensions. Here we give a method to extend some results on 2-colorings to Gallai-colorings, among them known and new, easy and difficult results.

175

Asteroids in rooted and directed path graphs

Kathie Cameron,  Chinh Hoàng,  Benjamin Lévêque

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.

174

Reusable containers within reverse logistic context

Chandoul Afif,  Van-Dat Cung,  Fabien Mangione

Due to economic and environmental constraints, many organizations have started to ship their products in reusable containers such as plastic pallets, boxes and crates. Minimizing the total flow cost arising from reusable containers is a major problem for these organizations. In this paper we will focus on the modeling of this problem as a network flow, and the proposal of an appropriate resolution method. This resolution method will allow us to better understand the system behavior and can be an important tool for studying related problems, such as dimensioning and purchasing policy.

173

Path partitions, cycle covers and max k-chromatic subgraphs: some known, some forgotten, some proven conjectures and integer decomposition of coflows

András Sebő

We first present pairs of assertions on path partitions in arbitrary digraphs, and on cycle covers in strongly connected graphs, connecting both objects to maximum $k$-chromatic subgraphs. We select analogies: statements that hold for path partitions and at least do not admit a counterexample for cycle covers, and vice versa.
In this pairing, the mate of some theorems is a conjecture. The analogy puts forward some new conjectures, some of which are converted to theorems:
On the one hand, the assertions concerning cycle covers are almost all theorems, and form a round theory of a pyramid form: there is a general theorem implying the others. This is a minmax theorem on the maximum union of $k$ particular stable sets, and the minimum « value » of a cycle cover, where the definition of « value » depends on $k$.
The first presentation of the proof of this theorem (here in Haifa in 2006, and in Journal of Combinatorial Theory/B, 97 (4) (2007) 518-552) used network flows, polyhedral combinatorics — linear programming. We update that presentation by showing two different extremities: we provide a simplified polyhedral approach using Cameron and Edmonds’ coflow polyhedra subject to a general argument of Baum and Trotter on integer decomposition; to honor Marty Golumbic’s birthday and pure graph theory, in the talk we explain how this works in terms of direct algorithmic steps in the underlying graph.
On the other hand, concerning path partitions, most of the assertions remain conjectures. Some simpler and weaker results are proved here using the relations between path partitions and cycle covers.

172

On b-colorings in regular graphs

Mostafa Blidia,  Frédéric Maffray,  Zoham Zemir

We call “natural editing of algebraic expressions” the editing of algebraic expressions in their natural representation, the one that is used on paper and blackboard. This is an issue we have investigated in the Aplusix project, a project which develops a system aiming at helping students to learn algebra. The paper summarises first this project. Second it defines the notion of algebraic expression, and of representation of algebraic expression. After an exploration of 20 software systems which represent and edit algebraic expressions, the idea of natural editing of algebraic expressions (insertion, deletion, selection, cut, copy, paste, drag and drop) is presented, leading to the notion of “smart editor”.

171

Characterization of b-gamma-perfect graphs

Mostafa Blidia,  Ikhlef-Eschouf Noureddine,  Frédéric Maffray

A b-coloring is a proper coloring of the vertices of a graph such that each color class has a vertex that is adjacent to a vertex of every other color, and the b-chromatic number b(G) of a graph G is the largest k such that G admits a b-coloring with k colors. A Grundy coloring is a proper coloring with integers 1, 2, …, such every vertex has a neighbor of each color smaller than its own color, and the Grundy number gamma(G) of a graph G is the largest k such that G admits a Grundy coloring with k colors. An a-coloring is a proper coloring of the vertices of a graph such that the union of any two color classes is not an independent set, and the a-chromatic number psi(G) of a graph G is the largest k such that G admits an a-coloring with k colors. A graph is b-gamma-perfect if b(H)=gamma(H) holds for every induced subgraph of G. We study the relationship between b and gamma and characterize b-gamma-perfect graphs as a special subclass of P_4-free graphs. We also show how to compute b in polynomial time for every P4-free graph. We also characterize b-psi-perfect graphs.

170

A Decomposition Approach solving a Large Scale Service Network Design with Asset Management problem

Nicolas Teypaz,  Susann Schrenk,  Van-Dat Cung

In this paper, we address a complete freight transportation problem. The objective function consists of maximizing the carrier profit. It is not necessary to satisfy all demands but profitable demands should be satisfied globally or partially. The carrier needs to ensure a return on his vehicle investment: his vehicles must be neither under- nor over-used. To tackle this industrial problem, we present a model based on a formulation of the Service Network Design with Asset Management problem. Due to the difficulty of finding optimal solutions to this problem, we propose a decomposition of the problem into three main steps: construction of the network, filling vehicles with commodities, construction of the vehicle planning. The resolution of these steps involves heuristic schemes, Mixed Integer Programming and Constraint Programming. We consider different methods for solving these steps and whether to allow transhipment. To evaluate the model and the solution algorithms, we produced instances based on a study of real data. The results show that the methods are robust without transhipment and that transhipment can improve profit.

169

Natural Editing of Algebraic Expressions

Jean-François Nicaud,  Denis Bouhineau

We call “natural editing of algebraic expressions” the editing of algebraic expressions in their natural representation, the one that is used on paper and blackboard. This is an issue we have investigated in the Aplusix project, a project which develops a system aiming at helping students to learn algebra. The paper summarises first this project. Second it defines the notion of algebraic expression, and of representation of algebraic expression. After an exploration of 20 software systems which represent and edit algebraic expressions, the idea of natural editing of algebraic expressions (insertion, deletion, selection, cut, copy, paste, drag and drop) is presented, leading to the notion of “smart editor”.

168

Graph transformations preserving the stability number

Benjamin Lévêque,  Dominique De Werra

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.

167

Multiflow Feasability : an Annotated Tableau

Guyslain Naves,  András Sebő

We provide a tableau of 189 entries and some annotations presenting the computational complexity of integer multiflow feasibility problems; 25 entries remain open. The tableau is followed by an introduction to the field, providing more problems and reproving some results with new insights, simple proofs, or slight sharpenings motivated by the tableau, paying particular attention to planar (di)graphs with terminals on the boundary. Last, the theorems that played a key-role in establishing the tableau are listed.

166

Characterizing path graphs by forbidden induced subgraphs

Benjamin Lévêque,  Frédéric Maffray,  Myriam Preissmann

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property.

165

Graph decomposition into paths under length constraints

Nicolas Teypaz,  Christophe Rapine

Given 2 integers a ? b, we define an (a, b)-decomposition of a graph G = (V , E ) as a partition of E into paths where the length of each path lies between a and b. In this definition paths are requested to be simple but not necessarily elementary. In other words an (a, b)-decomposition corresponds to a partition E1 , . . . , Ek of E with a ? ¦Ei ¦ ? b for all i, and such that each induced subgraph (Vi , Ei ) admits an Eulerian path. In this paper we investigate the complexity of the (a, b)-decomposition problem. We give a characteri- zation of (2, b)-decomposable graphs, from which it is possible to decide in linear time the (2, b)-decomposition problem. When a ? 3, we identify 2 classes of graphs, trees and Eulerian graphs, for which the (a, b)-decomposition problem remains polynomial. However we prove that the (3, 3)-decomposition problem is N P -complete, even on bipartite graphs. We give some evidence to conjecture that the more general H-decomposition problem into a given family H = {H1 , . . . , Hn } of connected graphs is N P -complete if and only if all Hi -decomposition problems are N P -complete.

164

Alternatives for Testing Total Dual Integrality

Edwin O’Shea,  András Sebő

In this paper we provide characterizing properties of TDI systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to $1$. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here.

In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.

163

Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility

We consider a scheduling problem that arises from an industrial application in chemical experimentations, where a single machine can process a fixed number of compatible jobs simultaneously. The precedence graph is restricted to be a disjoint union of chains, and the compatibility constraints are given by a partition of the tasks. Nevertheless, with these restrictions we prove the NP-completeness of the problem when the machine has a capacity of two, implying the difficulties for greater capacities. We also present a short proof for an infinite capacity. Our results also show the NP-completeness of the {sc D-Supersequence} problem, even when there are only two kinds of strings. We show polynomiality results when the number of chains in the precedence graph is fixed or when each chain has only two jobs. Results are summarized in a table given at the end of the article.

162

Recent results on well-balanced orientations

Attila Bernáth,  Satoru Iwata,  Tamás Király,  Zoltán Király,  Zoltán Szigeti

In this paper we consider problems related to Nash-Williams’ Strong Orientation Theorem and Odd-Vertex Pairing Theorem. These theorems date to 1960 and up to now not much is known about their relationship to other subjects in graph theory. We investigated many approaches to find a more transparent proof for these theorems and possibly generalizations of them. In many cases we found negative answers: counter-examples and $NP$-completeness results. For example we show that the weighted and the degree-constrained versions of the well-balanced orientation problem are $NP$-hard. We also show that it is $NP$-hard to find a minimum cost feasible odd-vertex pairing or to decide whether two graphs with some common edges have simultaneous well-balanced orientations or not.

Nash-Williams’ original approach was to define best-balanced orientations with feasible odd-vertex pairings: we show here that not every best-balanced orientation can be obtained this way. However we prove that in the global case this is true: every smooth $k$-arc-connected orientation can be obtained through a $k$-feasible odd-vertex pairing.

The aim of this paper is to help to find a transparent proof for the Strong Orientation Theorem. In order to achieve this we propose some other approaches and raise some open questions, too.

161

On minimally b-imperfect graphs

Chinh Hoàng,  Cláudia Linhares Sales,  Frédéric Maffray

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes. The b-chromatic number of a graph $G$ is the largest integer $k$ such that $G$ admits a b-coloring with $k$ colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph $H$ of $G$. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list ${cal{F}}$ of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for several classes of graphs, namely diamond-free graphs, and graphs with chromatic number at most three.

Une b-coloration est une coloration des sommets d’un graphe telle que chaque couleur contient un sommet qui a des voisins dans toutes les autres couleurs. Le nombre b-chromatique d’un graphe est le plus grand entier k tel que le graphe ait une b-coloration en k couleurs. Un graphe est b-parfait si, pour chaque sous-graphe induit H de G, le nombre b-chromatique de H est égal à son nombre chromatique habituel. Nous donnons une liste de 22 graphes minimalement b-imparfaits et conjecturons qu’un graphe est b-parfait si et seulement si il ne contient pas un graphe de cette liste. Nous démontrons cette conjecture dans le cas des graphes sans diamants et des graphes 3-colorable.

160

Operator Non-Availability Periods

N. Brauner,  G. Finke,  V. Lehoux-Lebacque,  C. Rapine,  C. Potts,  V. Strusevich

In scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non-availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling algorithms.

159

Optimizing Diversity

Yannick Frein,  Benjamin Lévêque,  András Sebő

We consider the problem of minimizing the size of a family of sets G such that every subset of {1; … ; n} can be written as a disjoint union of at most k members of G , where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the minimum of ¦G ¦ so that every subset of {1; … ; n} is the union of two sets in G has been asked by Erdõs and studied recently by Füredi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n; k) for which n le 3 k holds, and some individual values of n and k.