Displaying similar documents to “Column-Generation in Integer Linear Programming”

Integer Programming Formulation of the Bilevel Knapsack Problem

R. Mansi, S. Hanafi, L. Brotcorne (2010)

Mathematical Modelling of Natural Phenomena

Similarity:

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that ...

An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function

José Luis Quintero, Alejandro Crema (2006)

RAIRO - Operations Research

Similarity:

The multiparametric min max 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of min max 0-1-IP problems which are related by having identical constraint matrix and right-hand-side vector. In this paper we present an algorithm to perform a complete multiparametric analysis relative to the objective function.

Column-generation in integer linear programming

Nelson Maculan, Marcos de Mendonça Passini, José André de Moura Brito, Irene Loiseau (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application...