In a transit authority bus depot, buses of different types arrive in the evening to be parked in the depot for the night, and then dispatched in the morning...

We consider a widespread solution method that consists of a column generation approach embedded in a branch-and-bound scheme to solve the multiple depot veh...

Usual graph classes, such as complete graphs, paths, cycles and stars, frequently appear as extremal graphs in graph theory problems. Here we want to turn t...

We consider a crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a ...

The variable neighborhood search metaheuristic is applied to the primal simple plant location problem and to a reduced dual obtained by exploiting the compl...

We consider vehicle routing and crew scheduling problems that involve a lexico- graphic bi-level objective function (for instance, minimizing first the numb...

The continuous location-allocation problem requires finding sites for <i>m</i> new facilities in the plane in order to serve <i>n</i> users such that the to...

Variable Neighborhood Search (VNS) is a recent and effective metaheuristic for solving combinatorial and global optimization problems. It is capable of esca...

The global <i>k</i>-means heuristic is a recently proposed (Likas et al. 2003) incremental approach for minimum sum-of-squares clustering of a set <i>X</i> ...

In this paper we develop a Variable neighborhood search (VNS) heuristic for solving Mixed-Integer Programs (MIP’s). It uses CPLEX, the general-purpose MIP s...

An upper bound is given on the variance of degrees of graphs with <i>n</i> vertices, <i>m</i> edges and maximum degree &Delta;. Particular cases of chemical...

The algebraic connectivity <i>a(G)</i> of a graph <i>G = (V,E)</i> is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) sys...

The uniting feature of combinatorial optimization and extremal graph theory is that in both areas one should &#64257;nd extrema of a function defined in most...

Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premisses and/or conclu...

Computer-assisted and automated conjecture-making in graph theory is reviewed, focusing on the three operational systems GRAPH, Graffiti and AutoGraphiX (AGX...

The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard probl...

Two ways for bounding <i>n</i>-variables functions over a box, based on interval evalu- ations of first order derivatives, are compared. The optimal Baumann...

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on r...

We consider the bilevel uncapacitated facility location problem with user preferences. It is known that this model may be reformulated as a one-level locati...

The multiprocessor scheduling problem with communication delays that we consider in this paper consists of finding a static schedule of an arbitrary task gra...