Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 119:
=== A separation oracle for the dual LP ===
We are given some ''m'' non-negative numbers <math>y_1,\ldots,y_m</math>. We have to decide between the following two options:
* For every feasible configuration, the sum of <math>y_i</math> corresponding to this configuration is at most 1; this means that '''y''' is feasible.
Line 130:
The knapsack problem can be solved by dynamic programming in pseudo-polynomial time: <math>O(n\cdot W)</math>, where ''n'' is the number of items and ''W'' is the number of different possible weights (for example, if all sizes are integers, then the runtime is <math>O(n\cdot B)</math>). To get a polynomial-time algorithm, we can use an FPTAS for the knapsack problem. For example, an FPTAS by Lawler<ref>{{Cite journal|last=Lawler|first=Eugene L.|date=1979-11-01|title=Fast Approximation Algorithms for Knapsack Problems|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.4.4.339|journal=Mathematics of Operations Research|volume=4|issue=4|pages=339–356|doi=10.1287/moor.4.4.339|issn=0364-765X}}</ref> finds a solution that is at least <math>(1-\epsilon)</math> times the optimal one, in time <math>O(n \log{1/\epsilon} + 1/\epsilon^4)</math> operations.
* If the approximate oracle returns a solution with value larger than 1, then <math>\mathbf{y}_t</math> is definitely infeasible, and the solution correspond to a configuration that violates a constraint '''a'''. We do a "feasibility cut", cutting the ellipsoid all points '''y''' for which <math>\mathbf{a}\cdot \mathbf{y} > 1</math>.
* If the approximate oracle returns a solution with value at most 1, then '''<math>\mathbf{y}_t</math>''' may or may not be feasible. However, we still do an "optimality cut": we cut from the ellipsoid all points '''y''' for which <math>\mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{y}_t</math>. {{Clarify|date=January 2022}}
Using the approximate separation oracle gives an approximate solution to the dual. In particular, for any tolerance ''t'', we can find a feasible solution '''y*''' to the dual LP, with <math>\mathbf{n}\cdot \mathbf{y^*} \geq
As a byproduct of this process, we can consider only the constraints that are activated during the run of the ellipsoid method; there are at most ''<math>M</math> ''such constraints. We add to these, the trivial constraints <math>0 \leq y_j \leq 1</math>. All the other constraints have no effect on the computation of the solution '''y*'''. We can eliminate even more constraints by running this procedure iteratively: we choose a set of constraints, remove them, and find an approximate solution of the dual without these constraints. If the new solution is within the tolerance ''t'' of the old solution, then the constraints are dropped; otherwise, they are retained and a new set of constraints is tried. It can be shown that, after sufficiently many attempts, we will get a dual LP with only ''m'' constraints, which has the same (approximate) solution as the original dual LP. The run-time is <math>O\left(m^8 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>. If the constraints to remove are chosen at random, then the run-time becomes <math>O\left(m^7 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>.
▲=== Solving the fractional LP ===
=== Solving the primal LP ===
By the [[Dual linear program|LP duality theorem]], the optimal value of the primal LP equals the optimal value of the dual LP; we denoted this optimal value by LOPT.
Karmarkar and Karp present an algorithm that, for any tolerance factor ''h'', finds a basic feasible solution of cost at most LOPT(I) + ''h'', and runs in time:
<math>O\left(S^8 \log{S} \log^2(\frac{S n}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>,
| |||