# Why this ILP and LP are equivalent?

Let's consider a competition with $$n$$ questions. Each question has a price $$p_i$$ and a score $$v_i$$. To advance to the next round of the competition, we need to accumulate a minimum score of $$D$$. We can purchase a question, answer it, and earn its score. Assuming we can answer any question we buy, which subset of questions should we select to achieve a minimum score of $$D$$ while minimizing the total cost of the questions?

This problem can be formulated as an integer linear programming problem: \begin{aligned} \text{minimize } \quad & \sum_{i=1}^n p_ix_i \\ \text{subject to }\quad & \begin{array}{c} \sum_{i=1}^n v_ix_i\geq D \\ x_i \in \{0,1\}, \forall{i}\in\{1,2,\dots,n\} \end{array} \end{aligned}

However, we can also consider its relaxation: \begin{aligned} \text{minimize } \quad & \sum_{i=1}^n p_ix_i \\ \text{subject to }\quad & \begin{array}{c} \sum_{i\in\{1,2,\dots,n\}\setminus A} v_i^Ax_i\geq D_A, \forall A\in S \\ 0\leq x_i\leq 1 , \forall{i}\in\{1,2,\dots,n\} \end{array} \end{aligned} In this case, $$S$$ is the set of all subsets of questions whose total score is less than $$D$$. Also, $$D_A=D-\sum_{i\in A}v_i$$ and $$v_i^A=\min\{v_i, D_A\}$$.

I'm struggling to understand why these two formulations are equivalent and why the second LP satisfies the constraints of the problem.

Any assistance or guidance would be greatly appreciated!

EDIT

For example suppose we have 3 problems:

1. $$(v_1=3, p_1=6)$$
2. $$(v_2=2, p_2=5)$$
3. $$(v_3=1.75, p_3=3.75)$$

And the minimum score we need is $$D=4.5$$. We can pick questions in $$2^3=8$$ ways. Total score earned from each strategy is:

1. $$\emptyset\rightarrow 0$$
2. $$\{1\}\rightarrow 3$$
3. $$\{2\}\rightarrow 2$$
4. $$\{3\}\rightarrow 1.75$$
5. $$\{1,2\}\rightarrow 5$$
6. $$\{1,3\}\rightarrow 4.75$$
7. $$\{2,3\}\rightarrow 3.75$$
8. $$\{1,2,3\}\rightarrow 6.75$$

As you can see, only strategies in 5,6 and 8 have total score at least $$D$$. So the other subsets are elements of $$S$$.

Now for example consider $$A=\{2,3\}\in S$$. We have: $$D_A=D-\sum_{i\in A}v_i=4.5-3.75=0.75$$ Then $$v_1^A=\min\{0.75, 3\}=0.75$$. So the constraint would be: $$0.75x_1\geq 0.75$$ And we should do like this for other elements of $$S$$ as well.

EDIT2

I think we should show constraints matrix of second formulation is totally unimodular. So we can conclude that the solution would be integer.

• Welcome to OR.SE. Would you please, give a simple example of the second formulation, specifically, the elements of $S$ and $v_{i}^A$? Commented Apr 5 at 12:30
• @A.Omidi Thanks for your comment. I edited the post. Commented Apr 5 at 14:21
• Cross-posted at math.stackexchange.com/questions/4893593/….
– prubin
Commented Apr 5 at 16:03

A good first step would be to show that the new inequalities are valid. Consider an arbitrary feasible solution to the original problem, and let $$A\subseteq [n]$$. Then $$\sum_{i=1}^n v_i x_i = \sum_{i\in A} v_i x_i + \sum_{i\not\in A} v_i x_i\ge D,$$ which implies that $$\sum_{i\not\in A} v_i x_i \ge D- \sum_{i\in A} v_i x_i \ge D- \sum_{i\in A} v_i=D_A.$$ If $$A\not\in S$$, then $$D_A\le 0$$ and the constraint is redundant. Now apply a standard binary presolve technique ($$\sum_j a_j x_j \ge b$$ implies $$\sum_j \min(a_j,b) x_j \ge b$$) to obtain $$\sum_{i\not\in A} \min(v_i,D_A) x_i\geq D_A \quad \text{for all A\in S}.$$