Jacques Desrosiers This paper describes a vector space decomposition algorithmic framework for linear programming guided by dual feasibility considerations. The resolution process moves from one basic solution to the next according to an exchange mechanism which is defined by a direction and a post-evaluated step size. The core component of this direction is obtained via the smallest … Read more
It is well known that any feasible arc-flow solution to a network problem defined on a graph $G = (N, A)$, where $N$ is the set of nodes whereas $A$ is the set of arcs, can be expressed using at most $|A| + |N|$ paths and cycles having nonzero flow, out of these, at most … Read more
This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the Improved Primal Simplex (IPS) algorithm which turns degeneracy into a possible advantage. The constraints of the original problem are dynamically partitioned based on the numerical values of the current basic variables. The idea is to work … Read more
Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more
Column generation has become a powerful tool in solving large scale integer programs. We argue that most of the often reported compatibility issues between pricing oracle and branching rules disappear when branching decisions are based on the reduction of the variables of the oracle’s domain. This can be generalized to branching on variables of a … Read more
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not found in textbooks, yet. We emphasize on the growing understanding of the dual point of view, which brought considerable progress to the column generation theory … Read more