2
$\begingroup$

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{equation} \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} \end{equation}$$

However, we can also consider its relaxation: $$\begin{equation} \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} \end{equation}$$ 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.

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

1 Answer 1

2
$\begingroup$

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$}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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