Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Configuration linear program
open-in-new
<p>The configuration linear program (configuration-LP) is a <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> technique used for solving <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problems. It was introduced in the context of the <a href="/facts/Cutting_stock_problem/aGw6fSEd">cutting stock problem</a>. Later, it has been applied to the <a href="/facts/Bin_packing/T67Qe934">bin packing</a> and <a href="/facts/Optimal_job_scheduling/XyUejB6y">job scheduling</a> problems. In the configuration-LP, there is a variable for each possible <i>configuration</i> - each possible <a href="/facts/Multiset/bPFJGMDo">multiset</a> of items that can fit in a single bin (these configurations are also known as <i>patterns</i>) . Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations. </p>