linear programmingoptimization
max : $w = |q^T y|$
subject to
$A y \leq b$
$y \geq 0$
Please describe how one could solve the non-linear programming prob. above by using linear programming methods.
I tried changing $y$ to $y' – y''$ in the constraints and $y' + y''$ for the objective function. However, my Excel solver says that "the cells do not converge". How should I solve this?
Thanks a bunch!
Yes, this is part of a set of standard tricks that can be used to linearize polynomial terms involving integer, and especially binary variables. There are lots of such transformations, and most good integer programming (and especially mixed integer nonlinear programming) texts summarize them.
The best way to understand the transformation is to take it on a case by case basis. First consider $\delta_i = 0$. The first set of inequalities guarantees in this case that $z_i = 0$ which is what we want, and all the other constraints are redundant. If $\delta_i = 1$, then the first set of inequalities simply enforces the bounds since $z_i = y_i$ in this case. Moreover, $1 - \delta_i = 0$ means that the last 2 constraints enforce $z_i = y_i$.
There might be other ways to transform the quadratic term. For instance you could use some Big M type models, but those are usually not desirable since they yield weak relaxations if you pick your Big M parameter wrong.
You can do away with some of the constraints if your objective function "pushes" your variables in the right direction.
You have made a typo at the exercise. $\text{It is "A builder has purchased 21,00}$ $\color{red}{0}$ $\text{square meters of land}$ $\text{on which it is planned to build... "}$
But you have written it at your constraint: $600X+300Y \leq 21,000 \ \ $ (Square meters Constraint)
If you use this constraint the problem is feasible. This is what I got by using the Excel solver:
Excel sheet with formulas
Input mask
Best Answer
To follow the advise given to you, consider two problems: $$ \begin{cases} w^+ &= q^Ty^+\to\max, \\ Qy^+&\leq0, \\ Ay^+&\leq b, \\ y^+&\geq 0. \end{cases} $$ and
$$ \begin{cases} w^- &= q^Ty^-\to\max, \\ Qy^-&\geq0, \\ Ay^-&\leq b, \\ y^-&\geq 0. \end{cases} $$
Then $w = \max\{w^+,w^-\}$. Here matrix $Q = (q\quad0\quad\dots\quad0)^T$. With such decomposition you just consider two possible cases for the absolute value.