Search

Given a bipartite graph G = ( U ∪ V , E ) , | U | ⩽ | V | , the surplus of G is defined by the maximum number k such that a matching covering all vertices of U still exists upon removal of any k vertices from V . Given a partition U = { U 1 , … , U m } of U , the Multiple Bipartite Complete Matching Vertex Blocker Problem (MBCMVBP) consists in finding a partition V = { V 1 , … , V m } of V such that the smallest surplus among those of the induced subgraphs G [ U i ∪ V i ] is maximized. The removed vertices are related to the blocker notion. We show the strong NP-hardness of the MBCMVBP by using a reduction from the stable set problem. We also propose two integer linear programs for solving this problem. After comparing these two models, we introduce some valid inequalities for the model that outperforms the other one, and we analyze its facial structure. We then derive a Branch-and-Cut algorithm based on these results and conclude by an analysis of the experimental results.

In this paper we address unbalanced spatial distribution of hub-level flows in an optimal hub-and-spoke network structure of median-type models. Our study is based on a rather general variant of the multiple allocation hub location problems with fixed setup costs for hub nodes and hub edges in both capacitated and uncapacitated variants wherein the number of hub nodes traversed along origin-destination pairs is not constrained to one or two as in the classical models.. From the perspective of an infrastructure owner, we want to make sure that there exists a choice of design for the hub-level sub-network (hubs and hub edges) that considers both objectives of minimizing cost of transportation and balancing spatial distribution of flow across the hub-level network. We propose a bi-objective (transportation cost and hub-level flow variance) mixed integer non-linear programming formulation and handle the bi-objective model via a compromise programming framework. We exploit the structure of the problem and propose a second-order conic reformulation of the model along with a very efficient matheuristics algorithm for larger size instances.

World Congress on Computer Applications and Information Systems (WCCAIS), Hammamet, TUNISIA, JAN 17-19, 2014; International audience; In this paper, we consider the single machine scheduling problem with an unexpected non-availability interval. The objective is to minimize the maximum lateness. We have to decide the scheduling of jobs without any knowledge of the machine non-availability interval. Hence, we consider two possible models related to this constraint: breakdown model and emergent-job model. In both cases, the starting time of the non-availability interval and the length of the interval are unknown. We show that no root 37+1/6=competitive online algorithm exists for the breakdown model and no 9/2+root 31-competitive online algorithm exists for the emergent model and we show the Jackson's rule can give a 2-approximation for the two models and this ratio is tight.

International audience; The well-known column generation scheme is often an efficient approach for solving the linear relaxation of large-size Covering Integer Programs (CIP). In this paper, this technique is hybridized with an extension of the best-known CIP approximation heuristic, taking advantage of distinct criteria of columns selection. This extension uses fractional optimization for solving pricing subproblems. Numerical results on a real-case transportation planning problem show that the hybrid scheme accelerates the convergence of column generation both in terms of number of iterations and computational time. The integer solutions generated at the end of the process can also be improved for a significant proportion of instances, highlighting the potential of diversification of the approximation heuristic.

The Job Shop Scheduling Problem is one of the most intractable NP-Hard combinatorial optimization problems. To solve optimally this problem in a reasonable computational time, we have to improve the lower and the upper bounds. In this paper we introduce a new lower bound to the job shop scheduling problem with min-sum criteria and compare two different genetic algorithms. The gap is computed by comparing the best upper bound with the lower bound.

The Column Generation approach is generally a high-performing approach to solve the linear relaxation of Covering Integer Programs (CIP).In this communication, we propose a hybrid column generation approach for large-size CIP that runs a greedy heuristic at appropriate iterations of the column generation process to complete subsets of columns accordingly to a given coverage threshold. This heuristic is an extension of the best-known CIP approximation heuristic of Dobson to the case when explicit enumeration of the set of columns is infeasible. This extension uses fractional optimization, namely the Dinkelback's algorithm, for solving combinatorial pricing subproblems.Numerical results on a real-case transportation planning problem show that the hybrid scheme improves the three main performance criteria of Column Generation: computational time, convergence in terms of number of iterations, and quality of integer solutions found from the last Restricted Master Program. A research paper associated to this talk is to appear in Computers and OR

This paper deals with generalizations of Dobson approximation algorithm and proposes its cooperation with Column Generation for large-size Covering Interger Programs

International audience; L'optimisation des ressources agricoles est une préoccupation croissante dans le contexte du développement durable. En effet, une mauvaise utilisation de ces ressources peut avoir un impact négatif sur le plan écologique. C'est dans ce contexte que nous nous intéressons à un problème de planification de production agricole dont l'objectif est de construire, sur un horizon de temps donné, des rotations culturales couvrant des demandes saisonnières en diverses cultures et minimisant la surface totale des parcelles utilisées. Nous considérons particulièrement l'aspect stratégique de la planification sur un horizon long jusqu'à 60 saisons et nous proposons une approche de modélisation implicite engendrant un programme mathématique de grande taille. Un schéma de résolution hybride combinant l'approche de génération de colonnes et une heuristique est alors considéré. Les résultats numériques prouvent l'efficacité de ce schéma comparativement à une approche de résolution exacte du modèle explicite équivalent.

The NP-hard Covering Integer Programming minimization problem models manyreal-case applications. Covering Integer Programs can appear as basic models in someapplications like location problems, but also as master problemsresulting from a Dantzig-wolfe decomposition in other applications liketransportation problems, cutting stock problems, etc. In this work, we focus on the second category of large-size covering integer programs, for which the column generation method isgenerally an appropriate solving approach. However, as it provides only a lowerbound of the optimal solution, it is often combined with other solving approaches toobtain integer solutions. The main contribution of this work is a hybridization of an approximation heuristic and a classical approach based on column generation.Two real-case transportation and production applications are considered. The goal is not to design the best possible method for each problem but to show the added value of hybridization of given components. Experimental results on the two practical applications show that this combination improves the classical approach on three major criteria : average CPU time, number of iterations and quality of the integer value.

International audience; We propose in this paper a new Dantzig-Wolfe master model based on Lagrangian decomposition. We establish the relationship with classical Dantzig-Wolfe decomposition master problem and propose an alternative proof of the dominance of Lagrangian decomposition on Lagrangian relaxation dual bound. As illustration, we give the corresponding models and numerical results for two standard mathematical programs: the 0-1 bidimensional knapsack problem and the generalized assignment problem.

We deal in this paper with an agricultural production planning problem where crops must be scheduled on land plots so as to satisfy crop demands every period of time and to minimize the overall surface of land used for cultivation. This problem can be formulated as a covering integer program with a huge number of variables. A resolution scheme based on column generation is thus proposed, where the resulting pricing problem is efficiently solved by dynamic programming. The numerical experiments show that the method is all the more so efficient and robust as the planning horizon is long and plot sizes are small.

International audience; An efficient use of dynamic programming requires a substantial reduction of the number of labels. We propose in this paper an efficient way of reducing the number of labels saved and dominance computing time. Our approach is validated by experiments on shortest path problem with time windows instances.

International audience

International audience

We want to solve exactly large instances of the 0-1 quadratic knapsack problem with a branch-and-bound algorithm. Thus we need to obtain good lower and upper bounds in order to fix variables in the preprocessing phase at the root node of the search tree. We introduce reoptimization technics in this preprocessing phase using the lagrangian relaxation of Caprara, Pisinger and Toth and the lagrangian decomposition of Billionnet and Soutif. Reoptimization technics are used to reduce importantly (up to 60%) the number of iterations in the linear knapsack resolutions done in both lagrangian methods.

The 0-1 quadratic knapsack problem consists in maximizing a quadratic function subject to a linear capacity constraint. To solve exactly this problem with a branch and bound algorithm, we need to obtain good lower an upper bounds in order to fix a lot of variables in the pre-treatment phase at the root node of the branch and bound tree if we want to solve large instances. We introduce reoptimization technics in this pre-treatment phase using the lagrangean relaxation of Caprara, Pisinger and Toth and the lagrangean decomposition of Billionnet and Soutif that give the best upper bounds known today. Reoptimization technics are used to reduce importantly (until 60%) the number of iterations in the linear knapsack resolutions done in both lagrangean methods.

Outils d'analyse numérique pour l'automatique