1
$\begingroup$

Suppose there is an integer programming problem:

$$\min_{x_i \in \{0,1 \}, i=1,\cdots,k} \sum_{i=1}^k c_i x_i$$ subject to $$ \sum_{i=1}^k a_i x_i \leq W. $$

Suppose the cost coefficients are negative, i.e., $c_i < 0, i=1, \cdots, k$. I was wondering if it is possible to convert the problem to another with the same form, so that the cost coefficients are nonnegative and the minimization solutions are still the same?

I have thought about the conversion $c_i \mapsto c_i - \min_{j=1}^k c_j$. But it changes the solution.

Thanks in advance!

$\endgroup$
1
$\begingroup$

Try using $1-x_i$ instead of $x_i$.

$\endgroup$

Your Answer

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

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