1
$\begingroup$

I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-complete, but I suspect my instance can be solved in polynomial time; which of course does not contradict the hardness of the general 0-1 IP.

Given are a set of variables $S = \{s_0, \dots, s_n\}$, a set of values $V = \{v_0, \dots, v_m\}$, a set of costs $C = \{c_0, \dots, c_m\}$ (where each $v_j, c_j \in \mathbb{Z^+}$), and a positive integer $K$. Assume the values in $V$ and costs in $C$ are sorted, so that the last value in $V$ is the highest, and has the highest corresponding cost.

The optimization version of this problem asks which assignment of $v_j$ to $s_i$ has the lowest cost, where the sum is at least $K$? In addition, each $s \in S$ can only hold one $v \in V$.

To formulate this as a 0-1 IP, we construct a set of binary decision variables. Let this set be $X=\{x_{00},x_{01}, \dots, x_{0m}, \dots, x_{nm}\}$, where $x_k \in \{0, 1\}$ denotes if $v_j$ has been assigned to $s_i$. We then get the constraints:

$$\sum_{j=0}^{m}x_{ij} \leq 1 \quad \forall i=0,1,\dots,n$$ where the last constraint makes sure the sum is at least $K$: $$\sum_{j=0}^{m}x_{ij}v_j \geq K \quad \forall i=0,1,\dots,n$$ The 0-1 IP can then be formulated in its canonical form as: \begin{align} &\text{min} & & c^Tx \\ &\text{s.t} & & Ax \leq b \\ & & & x \geq 0 \end{align} Note that in this represntation, $C$ and $X$ are denoted $c$ and $x$ as they are vectors.

The decision version of this problem asks wether there exists a solution which satisfies $Ax \leq b$. This can be done in polynomial time by setting $x_{im} = 1 \quad \forall i = 0,1,\dots, n$, i.e., every $s \in S$ is assigned the highest value. If the sum of these values are at least $K$, then the answer is "yes", i.e., there is a solution which satisfies $Ax \leq b$. If "no", then there is no solution, because the highest possible sum has been tested.

My question: Since the decision problem can be solved in polynomial time, does it imply that the optimization problem also can be solved in polynomial time? For instance, if the size of $S$ is large, there may be trillions of solutions that satisfy $Ax \leq b$. My knowledge regarding how optimization algorithms work is limited, but as far as I understand, the solution space is 'fixed', so an algorithm would 'only' have to compare the solutions against each other to find the optimal one.

Lastly, I did not use the set $C$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

I have also read the follwing stackexchange posts:

$\endgroup$
2
  • $\begingroup$ I don't understand the problem you're trying to solve. What is the "cost" of an assignment? How does it relate to $C$? You talk about the "sum" being at least $K$, but sum of what? Can you express this as an instance of an assignment problem? $\endgroup$
    – D.W.
    Apr 14 at 19:51
  • $\begingroup$ I $s_i$ takes $v_j$, then it costs $c_j$. The "sum" refers to the sum of all s being at least K. $\endgroup$ Apr 16 at 11:03

2 Answers 2

2
$\begingroup$

Lastly, I did not use the set $𝐢$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

It is not correct, indeed :)

You are describing a decision problem, but it does not correspond to your optimization problem. One of the questions you posted (Optimization version of decision problems) explains that quite nicely. Quoting the shortest path example from there:

optimization/search version: Given an undirected unweighted graph $𝐺=(𝑉,𝐸)$ and two vertices $𝑣,π‘’βˆˆπ‘‰$ , find a shortest path between $𝑣$ and $𝑒$ .

decision version: Given an undirected unweighted graph $𝐺=(𝑉,𝐸)$ , two vertices $𝑣,π‘’βˆˆπ‘‰$ , and a non-negative integer $π‘˜$ , is there a path in $𝐺$ between $𝑒$ and $𝑣$ whose length is at most π‘˜

The emphasized part is what you are missing. The corresponding decision problem is not about finding any solution for the optimization problem. Instead, it is about finding a solution that is at least as good as $π‘˜$ for some constant $π‘˜$.

So, in your example, you should replace this sentence

The decision version of this problem asks wether there exists a solution which satisfies $𝐴π‘₯≀𝑏$ .

with this

The decision version of this problem asks wether there exists a solution which satisfies $𝑐^𝑇π‘₯≀k$ (and, of course, still satisfies $𝐴π‘₯≀𝑏$) .

to get the correct corresponding decision problem.

Now, if the decision problem is in $P$, you can invoke its polynomial algorithm several times for increasing $k$ and in a binary search manner you will find the answer for the corresponding optimization problem. So, you solved that in polynomial time, too.

$\endgroup$
2
$\begingroup$

Often, if the decision problem can be solved in polynomial time, the optimization problem can be solved in polynomial time as well. For example, if you could decide in polynomial time if a problem has a solution with at most a certain cost, you may be able to binary search for the minimal possible cost.

Your decision problem, however, does not have any restrictions on the cost, and can therefore not be exploited to solve the optimization problem in polynomial time. (In fact, your optimization problem is NP-hard as it can be reduced from the unbounded knapsack problem.)

$\endgroup$
5
  • $\begingroup$ Doesn't the unbounded knapsack problem just state that any repetition of items are allowed; meaning, it is still a knapsack problem with some budget constraint (which is not present in my formulation). $\endgroup$ Apr 16 at 11:09
  • $\begingroup$ Of course the problems are not exactly the same. They have an upper bound on the cost, while you have a lower bound on the value. However if you can solve your problem, you can solve the unbounded knapsack problem by binary searching for the highest $K$ which gives a low enough cost. Another difference is that you use exactly $n$ items. However, note that if you set $n = K$ and add an item with 0 cost and value (you can also use values in $\mathbb{Z}^+$ but it is a bit more complicated), the constraint on the number of items does not matter anymore $\endgroup$
    – 1001
    Apr 16 at 11:38
  • $\begingroup$ Interesting, I would have to read a bit on that. I am however not using exactely $n$ items, but at most $n$ (not sure if that makes any difference regarding your answer). $\endgroup$ Apr 16 at 11:48
  • $\begingroup$ In that case you don't have to add the extra "empty" item. $\endgroup$
    – 1001
    Apr 16 at 11:51
  • $\begingroup$ I have been digesting your answer for some time now, and I have a few questions. 1. Regarding the reduction from UKP, is it the 'unlimited' supply ($n$) of $v_j$ that made you consider that specific reduction? 2. How does the set $S$ come into play when formulating the UKP/KP; what are the 'items' in this formulation (only $V$, or assignments of $V$ to $S$)? 3. How can this be formulated as a UKP/KP when there is no bound on the cost? The only formulation I've come across is the "Minimization Knapsack Problem" which is presented in "Knapsack Problems" (Kellerer et.al 2004). $\endgroup$ Apr 17 at 12:38

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.