Delayed column generation is an efficient algorithm for solving larger linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non-basic and assume a value of zero in the optimal solution, only a subset of variables need to be considered when solving the problem.

PropertyValue
dbpprop:abstract
  • Delayed column generation is an efficient algorithm for solving larger linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non-basic and assume a value of zero in the optimal solution, only a subset of variables need to be considered when solving the problem. Column generation leverages this idea to generate only the variables which have the potential to improve the objective function--that is, to find variables with negative reduced cost (assuming without loss of generality that the problem is a minimization problem). The problem being solved is split into two problems: the master problem and the subproblem. These are sometimes referred to as the primary (primal) and secondary (dual) problems, respectively. The master problem is the original problem with only a subset of variables being considered. The subproblem is a new problem created to identify a new variable. The objective function of the subproblem is the reduced cost of the new variable with respect to the current dual variables, and the constraints require that the variable obey the naturally occurring constraints. The process works as follows. The master problem is solved--from this solution, we are able to obtain dual prices for each of the constraints in the master problem. This information is then utilized in the objective function of the subproblem. The subproblem is solved. If the objective value of the subproblem is negative, a variable with negative reduced cost has been identified. This variable is then added to the master problem, and the master problem is re-solved. Re-solving the master problem will generate a new set of dual values, and the process is repeated until no negative reduced cost variables are identified. The subproblem returns a solution with non-negative reduced cost, we can conclude that the solution to the master problem is optimal. In many cases, this allows large linear programs that had been previously considered intractable. The classical example of a problem where this is successfully used is the cutting stock problem. One particular technique in linear programming which uses this kind of approach is the Dantzig-Wolfe decomposition algorithm. Additionally, column generation has been applied to many problems such as crew scheduling, vehicle routing, and the capacitated p-median problem.
  • La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l'ensemble des contraintes en deux sous ensembles. L'idée centrale est que les programmes linéaires de grande taille ont trop de variables pour qu'on puisse les représenter toutes de manière explicite. A l'optimum, la plupart des variables sont hors base et, très souvent, la plupart d'entre elles sont nulles, c'est-à-dire que seul un (petit) sous-ensemble de variables doit être pris en compte pour résoudre le problème. Une méthode utilisant la génération de colonnes initialise le programme linéaire avec un sous-ensemble de colonnes de petite taille. Le mécanisme de la génération de colonnes consiste alors à générer, au sein d'un algorithme à plusieurs étapes, les variables qui sont susceptibles d'améliorer la solution courante, c'est-à-dire celles qui ont des coûts réduits négatifs. L'efficacité de la méthode est très dépendante du mécanisme utilisé pour générer des colonnes. En effet, le sous-problème à résoudre est souvent NP-difficile. Les méthodes utilisant la génération de colonnes ont souvent des problèmes de convergence dû au fait que le problème dual est très peu contraint au début de la méthode. En pratique, ces problèmes vont amener la méthode à effectuer un grand nombre d'itérations qui ne permettent plus d'améliorer la solution courante.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • Delayed column generation is an efficient algorithm for solving larger linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non-basic and assume a value of zero in the optimal solution, only a subset of variables need to be considered when solving the problem.
  • La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l'ensemble des contraintes en deux sous ensembles. L'idée centrale est que les programmes linéaires de grande taille ont trop de variables pour qu'on puisse les représenter toutes de manière explicite.
rdfs:label
  • Delayed column generation
  • Génération de colonnes
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of