Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Column_generation> ?p ?o }
Showing triples 1 to 36 of
36
with 100 triples per page.
- Column_generation abstract "Column generation or 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 in theory 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. 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 to be solved. 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.".
- Column_generation wikiPageID "744589".
- Column_generation wikiPageLength "2579".
- Column_generation wikiPageOutDegree "10".
- Column_generation wikiPageRevisionID "624813613".
- Column_generation wikiPageWikiLink Capacitated_p-median_problem.
- Column_generation wikiPageWikiLink Category:Optimization_algorithms_and_methods.
- Column_generation wikiPageWikiLink Crew_scheduling.
- Column_generation wikiPageWikiLink Cutting_stock_problem.
- Column_generation wikiPageWikiLink Dantzig–Wolfe_decomposition.
- Column_generation wikiPageWikiLink Linear_programming.
- Column_generation wikiPageWikiLink Mathematical_optimization.
- Column_generation wikiPageWikiLink Optimization_(mathematics).
- Column_generation wikiPageWikiLink Reduced_cost.
- Column_generation wikiPageWikiLink Vehicle_routing.
- Column_generation wikiPageWikiLink Vehicle_routing_problem.
- Column_generation wikiPageWikiLink Without_loss_of_generality.
- Column_generation wikiPageWikiLinkText "''column'' generation".
- Column_generation wikiPageWikiLinkText "Column generation".
- Column_generation wikiPageWikiLinkText "column generation".
- Column_generation hasPhotoCollection Column_generation.
- Column_generation wikiPageUsesTemplate Template:Mathapplied-stub.
- Column_generation wikiPageUsesTemplate Template:Optimization_algorithms.
- Column_generation subject Category:Optimization_algorithms_and_methods.
- Column_generation hypernym Algorithm.
- Column_generation type Software.
- Column_generation type Algorithm.
- Column_generation comment "Column generation or 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 in theory when solving the problem.".
- Column_generation label "Column generation".
- Column_generation sameAs Génération_de_colonnes.
- Column_generation sameAs m.037qyl.
- Column_generation sameAs Генерация_столбцов.
- Column_generation sameAs Q3123181.
- Column_generation sameAs Q3123181.
- Column_generation wasDerivedFrom Column_generation?oldid=624813613.
- Column_generation isPrimaryTopicOf Column_generation.