Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,y_1,y_2\ge0$ and $x_1+x_2=y_1+y_2=1$. The idea is to introduce auxiliary variables $z_{ij}$ and maximize $$\sum_i\sum_ja_{ij}z_{ij}$$ subject to $z_{ij}\le x_i$ and $z_{ij}\le b_{ij}y_j$.
It's been a while since I thought about linear optimization. If I remember correctly, the constraints usually need to be of the form $Ax\le b$ (or $Ax=b$), where $A$ and $b$ are constant. How can I rewrite the problem in such a "standard" form?
I would like to solve this problem with GLPK (just as a starting point for my understanding how this library works). So, if anyone knows how the constraints above can be specified in the API I would be very thankful.
EDIT: My guess is we need to consider $$\underbrace{\begin{pmatrix}1&1&0&0&0&0&0&0\\ 0&0&1&1&0&0&0&0\\ -1&0&0&0&1&0&0&0\\ -1&0&0&0&0&1&0&0\\ 0&-1&0&0&0&0&1&0\\ 0&-1&0&0&0&0&0&1\\ 0&0&-b_{11}&0&1&0&0&0\\ 0&0&0&-b_{12}&0&1&0&0\\ 0&0&-b_{21}&0&0&0&1&0\\ 0&0&0&-b_{22}&0&0&0&1\end{pmatrix}}_{=:\:A}\begin{pmatrix}x_1\\x_2\\y_1\\y_2\\z_{11}\\z_{12}\\z_{21}\\z_{22}\end{pmatrix}\begin{pmatrix}=1\\=1\\\le0\\\le0\\\le0\\\le0\\\le0\\\le0\\\le0\\\le0\end{pmatrix}$$ or (if we need to eliminate the inequality constraints by introducing further auxiliary variables $u_{ij},v_{ij}\ge0$) $$\underbrace{\begin{pmatrix}1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&1&1&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0\\ -1&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0\\ 0&-1&0&0&0&0&1&0&0&0&1&0&0&0&0&0\\ 0&-1&0&0&0&0&0&1&0&0&0&1&0&0&0&0\\ 0&0&-b_{11}&0&1&0&0&0&0&0&0&0&1&0&0&0\\ 0&0&0&-b_{12}&0&1&0&0&0&0&0&0&0&1&0&0\\ 0&0&-b_{21}&0&0&0&1&0&0&0&0&0&0&0&1&0\\ 0&0&0&-b_{22}&0&0&0&1&0&0&0&0&0&0&0&1\end{pmatrix}}_{=:\:A}\begin{pmatrix}x_1\\x_2\\y_1\\y_2\\z_{11}\\z_{12}\\z_{21}\\z_{22}\\u_{11}\\u_{12}\\u_{21}\\u_{22}\\v_{11}\\v_{12}\\v_{21}\\v_{22}\end{pmatrix}=\begin{pmatrix}1\\1\\0\\0\\0\\0\\0\\0\\0\\0\end{pmatrix}.$$
Yes, your formulation is correct. Adapting the example from the introduction to GLPK, I get the following solution, which you may want to check.
GLPK Simplex Optimizer, v4.65 10 rows, 8 columns, 20 non-zeros 0: obj = -0.000000000e+00 inf = 2.000e+00 (2) 2: obj = -0.000000000e+00 inf = 0.000e+00 (0) * 7: obj = 2.820000000e-01 inf = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND objective = 0.282; x1 = 0.6; x2 = 0.4; y1 = 1; y2 = 0 z11 = 0.01; z12 = 0; z21 = 0.4; z22 = 0The code is as follows: