Return to Answer

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the [subset sum problem(https://en.wikipedia.org/wiki/Subset_sum_problem) or knapsack problem. In fact, it looks like this is a kind of reverse knapsack. If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$. That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack. The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem. The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$. If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the subset sum problem or knapsack problem. In fact, it looks like this is a kind of reverse knapsack. If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$. That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack. The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem. The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$. If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of subset sum problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the [subset sum problem(https://en.wikipedia.org/wiki/Subset_sum_problem) or knapsack problem. In fact, it looks like this is a kind of reverse knapsack. If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$. That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack. The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem. The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$. If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.

This looks like linear programming, but an extremely simple sort of linear programming with just one constraint (one inequality). OK, apparently you have a special case for the case where one or more of the $sel_i$'s are $1$, but that can be handled separately using case splitting.

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of subset sum problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.