2
$\begingroup$

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?

$\endgroup$
1
8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Clever thanks for sharing ! $\endgroup$ – Kuifje Jan 23 at 13:46
  • 1
    $\begingroup$ This is a fairly standard technique in for instance goal programming formulations. I guess there is more emphasis on algorithms in linear programming classes than on modeling. $\endgroup$ – Erwin Kalvelagen Jan 25 at 10:33
  • $\begingroup$ Mmm I don't know if its a matter of what is taught in classes. Perhaps it is, but also when modeling, there is often more than one way of doing things, and remembering all the tips and tricks out there can be challenging. When it comes to modeling, you use it or lose it. I think this is why this platform is great: it is a good way to keep practicing and staying in the loop. And having people with a lot of experience (like you) that can pinpoint pros and cons of different approaches is a real bonus. $\endgroup$ – Kuifje Jan 25 at 13:06
  • $\begingroup$ It is true that there is no grand unifying theory of modeling. But modeling is also not just a bag of tricks. $\endgroup$ – Erwin Kalvelagen Jan 25 at 13:22
6
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Duplicating expressions is not a good practice. This can be written as one constraint with two slacks. Of course for small models, it does not make a difference. $\endgroup$ – Erwin Kalvelagen Jan 22 at 19:02
  • $\begingroup$ thanks a lot for this solution, really it is useful. $\endgroup$ – Ali Jan 22 at 21:32
  • $\begingroup$ @ErwinKalvelagen Thanks for your insight, if you write your comment as an answer I will be happy to upvote it. $\endgroup$ – Kuifje Jan 22 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.