An equivalent model for exactly solving the multiple-choice multidimensional knapsack problem

The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) is a problem which can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions. In this paper, we investigate the use of a new model-based Lagrangian relaxation for optimally solving the MMKP. In order to tackle large-scale problem instances, we curtail the search process for providing approximate solutions. We then apply the Cplex solver using both original and equivalent models. In this case, the Cplex solver becomes more efficient when the new model is used. Also, when the proposed method is considered as a heuristic, then it outperforms the Cplex solver using the original model: new solution values are obtained.

Keywords: Heuristic; Knapsack; Lagrangian relaxation; Optimality.

Mhand Hifi and Lei Wu

source

Benchmark instances:

download (I1-13 and INST01-20)

Application d’un nouveau critère de robustesse pour le problème du plus court chemin

En optimisation, les sources d’incertitude et d’imprécision sont nombreuses et rendent souvent difficiles l’affectation d’une unique valeur plausible à chacun des paramètres du modèle. Il peut alors être plus pertinent de retenir un ensemble de valeurs possibles pour chacun des paramètres. Un scénario est défini en choisissant une unique valeur dans chacun des ensembles. Dans ce contexte, une solution robuste doit être aussi bonne que possible dans une grande majorité de scénarios et jamais trop mauvaise. Cette caractérisation donne lieu à de nombreuses interprétations possibles qui justifient différentes approches de la robustesse. Ces approches se distinguent par les différents modèles utilisés pour représenter les facteurs d’incertitude, par les méthodologies utilisées pour mesurer la robustesse, et finalement par la conception et l’analyse des méthodes de résolution. Dans ce papier, nous nous focalisons sur l’application de nouveaux critères pour le plus court chemin avec des valeurs incertaines sur les arcs. Nous commençons par rappeler deux modèles d’incertitude habituellement considérés : le modèle par intervalle et le modèle par ensemble discret de scénarios. Pour chacun d’entre eux, nous appliquons les nouveaux critères de robustesse appelés bw-robustesse et bw-déviation (proposés initialement par B. Roy) qui généralisent respectivement les critères du pire cas et du regret maximum. Dans chacun des cas, nous avons à résoudre des programmes linéaires en nombres entiers de très grandes tailles. Nos expérimentations numériques sur des graphes de grandes tailles montrent qu’un solveur standard de type Cplex est capable de résoudre ces nouveaux problèmes, ce qui est très prometteur du point de vue de l’analyse de robustesse.

Keywords: Robustness analysis; Shortest path problem; Worst case criterion; Integer linear programming.

Virginie Gabrel, Cécile Murat, Lei Wu

source

New models for the robust shortest path problem: complexity, resolution and generalization

In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients.

Keywords: Robustness analysis; Shortest path problem; Worst case criterion; Integer linear programming.

Virginie Gabrel, Cécile Murat, Lei Wu

doi:10.1007/s10479-011-1004-2