Consider a multidimensional knapsack problem, and let $M$ denote the number of knapsack constraints. I am trying to solve a problem where $M$ is exponential in the number of $0-1$ variables in my problem. I am interested in solving the multi-dimensional knapsack problem without enumerating all the $M$ constraints.

I am equipped with following tool: suppose I solve the knapsack problem with $m$ constraints, where $m < M$, I have a polynomial time oracle that outputs a violated knapsack constraint that was not included in those $m$ constraints.

If we assume that solving the knapsack problem takes $c$ time units (irrespective of the number of knapsack constraints), is it possible to devise an algorithm which sequentially adds a violated constraint by calling the polynomial oracle, s.t. the number of calls to the oracle can be bounded as a polynomial in the number of variables? For readers, familiar with the ellipsoid method with exponential constraints, the scheme describe above is analogous to adding a violated linear inequality and resolving until no more violated constraints can be found.

It would be helpful if someone can provide suggestions as to how to analyze this problem. In case you are wondering, I constructed this problem by enumerating all source-sink paths of a DAG, where the arcs themselves are $0-1$ variables, which need to satisfy some other constraints. The objective is to bound the length of the longest path on the DAG.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.