5
$\begingroup$

I have a list of thousands of linear expressions, with less than 100 total variables. Each expression is associated with a positive point value. I want to make as many of the expressions greater than zero as possible, maximizing the total points of the expressions I can make positive.

For example:
x1 + x2 > 0 (5 points)
x1 - 3*x2 > 0 (1 point)
-x1 + x2 > 0 (4 points)

I can choose x1=1, x2=2 to maximize the score (9 points).

Is there an established algorithmic approach to solve this kind of problem?

$\endgroup$
1
  • $\begingroup$ Sounds like some kind of greedy constraint satisfaction may work reasonably well (fail in bad cases) --- e.g., first satisfy the most valuable constraint, then the next and so on. Of course, this heuristic can easily fail for adversarially chosen constraints. Alternatively, it sounds like some kind of knapsack type of problem. $\endgroup$
    – Suvrit
    Oct 20, 2015 at 23:31

1 Answer 1

3
$\begingroup$

If the coefficients of your linear expressions are integers and you want the variables $x_i$ to be integers as well then the problem can be written as an integer program: \begin{align*} \text{Maximize }\sum_{i=1}^m&c_iy_i\\ \text{subject to }My_i &\leqslant M-1+\sum_{j=1}^na_{ij}x_j &&i\in\{1,\ldots,m\},\\ x_j &\in\mathbb{Z}&&j\in\{1,\ldots,n\},\\ y_i &\in\{0,1\} && i\in\{1,\ldots,m\}. \end{align*} Here $\displaystyle\sum_{j=1}^na_{ij}x_j$ is the $i$-th linear expression, $c_i$ is its point value, and $M$ is a sufficiently large number.

Throwing this formulation at a MIP solver might be worth a try.

$\endgroup$
0

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.