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?

Improve this question
$\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
    Commented Oct 20, 2015 at 23:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .