Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 111:
* Assert that '''y''' is feasible, that is, <math>A^T \mathbf{y} \leq \mathbf{1}</math>; or -
* Assert that '''y''' is infeasible, and return a specific constraint that is violated, that is, a vector '''a''' such that <math>\mathbf{a}\cdot \mathbf{y} > 1</math>.
The ellipsoid method starts with a large ellipsoid, that contains the entire feasible ___domain <math>A^T \mathbf{y} \leq \mathbf{1}</math>. At each step ''t'', it takes the center <math>\mathbf{y}_t</math> of the current ellipsoid, and sends it to the separation oracle:
* If the oracle says that <math>\mathbf{y}_t</math> is feasible, then we 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>. These points are definitely not optimal.
* If the oracle says that <math>\mathbf{y}_t</math> is infeasible and violates the constraint '''a''', then we do a "feasibility cut": we cut from the ellipsoid all points '''y''' for which <math>\mathbf{a}\cdot \mathbf{y} > 1</math>. These points are definitely not feasible.
After making a cut, we construct a new, smaller ellipsoid. It can be shown that this process converges to an approximate solution, in time polynomial in the required accuracy.
=== A separation oracle for the dual LP ===
Line 122 ⟶ 128:
* If the total value of the optimal knapsack solution is at most 1, then we say that '''y''' is feasible.
* If the total value of the optimal knapsack solution is larger than 1, then we say that '''y''' is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since <math>\mathbf{a}\cdot \mathbf{y} > 1</math> for the vector '''a''' that corresponds to this configuration).
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>).
Now, the ellipsoid method should be adapted to use an ''approximate'' separation oracle. Given the current ellipsoid center <math>\mathbf{y}_t</math>:
* 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 consider it a
* If the approximate oracle says that <math>\mathbf{y}_t</math> is feasible, then we 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>. These points are definitely not optimal.
*
After making a cut, we construct a new, smaller ellipsoid. It can be shown that this process converges to an approximate solution, in time polynomial in the required accuracy.
* If the approximate oracle returns a solution with value larger than 1, then '''y''' is definitely infeasible, and the solution correspond to a configuration that violates a constraint.
*
=== Solving the fractional LP ===
| |||