I have an optimization problem which I hope I can formulate as a linear program. The problem involves a vector $x$ of binary decision variables (so each entry of the $x$-vector is either $0$ or $1$). The goal is to
$$\text{maximize}\ c^Tx$$
where $c$ contains positive constants that are given by the problem. Furthermore I have a single constraint
$$ d^Tx \le_{soft} K $$
where $d$ is a vector also containing positive constants and $K$ is an upper bound. Both are given by the problem.
Now here is where my problem lies. The inequality in the constraint is not a normal inequality, meaning that the limit $K$ can be exceeded, hence I called it "soft" constraint. Let's say we choose $n$ of the $x$'s as $1$ and the sum of all the corresponding $d$'s does not exceed $K$, then we are allowed to choose one more entry of the $x$ vector. So
$$ \sum_{i=1}^{n} d_i\cdot x_i \le K \quad \text{but}\quad \sum_{i=1}^{n+1} d_i\cdot x_i \substack{\ge \\ \gt} K \\ $$
$$ \text{(this is illustrative as there is no concrete summation and any of the $x$'s can be chosen)} $$
I think an example would probably make it clearer. Let's say we have the vector $d = [4\ 5\ 2]^T$ and $x = [a\ b\ c]^T \text{ where } a ,b,c \in \{0,1\}$ and the constant $K = 5$. As I just want to reformulate the constraint the vector $c$ is unnecessary in this example.
The combination $x = [0\ 1\ 1]^T$ should be valid since the sum $0\cdot 4 + 1 \cdot 5 + 1 \cdot 2 = 7$ is greater than 5 but as soon as we leave one more x out (either $5$ or $2$) the constraint is satisfied $d^Tx \le 5 \text{ with } x = [0\ 0\ 1]^T \text{ or } x = [0 \ 1\ 0]^T$.
The same goes for the vectors $x = [0\ 0\ 0]^T, [1\ 0\ 0]^T, [0\ 1\ 0]^T, [0\ 0\ 1]^T, [1\ 1\ 0]^T$ but not for $x = [1\ 1\ 1]^T$ since the dot product $d^Tx$ is always greater than $5$ no matter which of the $x$'s we chose to leave out ($x = [0 \ 1\ 1] \implies 7 \gt 5$, $x = [1 \ 0\ 1] \implies 6 \gt 5$, $x = [1 \ 1\ 0] \implies 9 \gt 5$).
Now my question. Can something like this be formulated as a linear program? My gut feeling is that it should be but I don't know how. If it is not possible is there another way to solve a problem like this?
I don't know if I have formulated everything as I'm new to linear programming. Thanks for your help.
You could introduce another vector of binary decision variables $y$ with the same dimension as $x$, that will represent which element of the bag to "remove" to get the overall weight down to or below the capacity $K$. We are only allowed to leave out one element so we add the constraint $\vec{1}^Ty=1$ where $\vec{1}$ is the vector of all ones. Also, we can't leave an element we didn't take, so we add the constraint $y \leq x$. Thus your problem can be formulated as the following Integer Program: \begin{align} \max&& c^Tx \\ \text{subject to}&& d^Tx-d^Ty &\leq K \\ &&\quad\ \vec{1}^Ty &\leq 1 \\ && y &\leq x \\ && x, y &\in \{0,1\}^n \\ \end{align}