Hard to soft constraint

Question

What are all necessary changes to the below model so that constraint set $(2)$ becomes soft?

Give the new full model. $\alpha_{ij}$ are parameters. Eqn. $(1)$ refers to an already existing function of the decision variables that is being maximized.

\begin{align} \max\limits_{x\in \mathbb{R^{m\times n}}}&\quad f(x) \tag{1} \\ \text{s.t.}&\quad\sum_{i=1}^m a_{ij}x_{ij}=10 &\forall j=1,\ldots,m \tag{2} \\&\quad x_{ij}\ge 0 & \forall i=1,\ldots,m,\; \forall j=1,\ldots,n \tag{3} \end{align}

What will change if the problem becomes a minimization problem?

Answer 1

My approach would be: $$\begin{align} \min\>&- f(\color{darkred}x)+\sum_j \color{darkblue}p^-_j \color{darkred}s^-_j +\sum_j \color{darkblue}p^+_j \color{darkred}s^+_j\\ &\sum_i \color{darkblue}a_{i,j}\color{darkred}x_{i,j} = 10 -\color{darkred}s^-_j + \color{darkred}s^+_j&&\forall j\\ &\color{darkred}s^-_j,\color{darkred}s^+_j \ge 0 \end{align}$$ where $\color{darkblue}p$ are penalties and $\color{darkred}s$ are slack variables. This prevents duplicating the terms $\sum_i \color{darkblue}a_{i,j}\color{darkred}x_{i,j}$ (incurring possibly a large number of nonzero elements) and may also convey more clearly that we are making just one equality constraint elastic.

Answer 2

To make constraint (2) soft, you can proceed as follows. Transform the constraint into two inequalities (2a) and (2b), add non negative variables $\varepsilon_{kj}$, $k\in \{1,2\}$ to allow violation, and minimize the violation in the cost function : $$ \max\limits_{x\in \mathbb{R^{m\times n}}}\quad f(x) - \sum_{k,j}\varepsilon_{kj} $$ subject to \begin{align} &\sum_{i=1}^m a_{ij}x_{ij}\le10 + \varepsilon_{1j} &\forall j=1,\ldots,m \tag{2a} \\ &\sum_{i=1}^m a_{ij}x_{ij}\ge10 - \varepsilon_{2j} &\forall j=1,\ldots,m \tag{2b} \end{align}

Depending on how much violation is allowed, you might want to add weights to variables $\varepsilon_{kj}$. You might also want to consider minimizing $\max\{\varepsilon_{kj}\}$ instead.

Now if this is homework, I will leave you with question 2, which you should be able to easily answer if you understand the spirit of the above strategy.