Recently I've been looking into optimization, to try and solve the following problem.
We have several sorts of factory. Each factory-type takes some amount of goods, and produces other goods. The optimisation problem is to try and meet every factory's internal consumption, while overall producing more that $d$, the external demand, of each good. Additionally, we want an integer amount of factories.
Here's a very simple example: We specify production with a matrix $$ \begin{pmatrix} 2 & -4 \\ 0 & 1 \\ 0 & 1 \end{pmatrix} $$ An interpretation could be: A farm makes 2 milk. A dairy takes 4 milk, and makes 1 cheese and 1 pasteurized milk.
If the demand vector is $d = (0 \ \ 2 \ \ 2)^\mathsf{T}$, then the solution will be $x = (4 \ \ 2)^\mathsf{T}$.
Now, up until this point, this is a LP, and can be solved using standard solvers.
The complication is this: the more factories we have, the greater efficiency in inputs and outputs we have. This scaling factor is specified by the following sort of function.
The idea is that, in the polynomial part, you are benefiting from economies of scale. But after a certain point, you do not get any more multiplicative advantage from placing the factories near each other.
The linear program, abstractly specified, would look something like this:
Let $f$ be the scaling function, $$\begin{aligned} & \mathbf{minimize}(x)\ \ \sum_i (A (f \circ x))_i \\ & \mathbf{subject\ to} \\ &\quad A (f \circ x) \geq d \\ &\quad x_j \geq 0 &(1 \leq j \leq n) \\ &\quad x_j \in \mathbb{Z} &(1 \leq j \leq n) \end{aligned}$$ where $A$ is a matrix, $x$ the input vector we want to minimise, and $\circ$ means element-wise application. (i.e. $f\circ(a_1, a_2, \dots) = (f(a_1), f(a_2), \dots)$.)
My questions are these:
Can the problem, thus specified, be solved 'efficiently'? (Efficiently not in the abstract complexity sense, but in the sense of: a reasonably sized problem can be given to a solver and it takes less than an hour to finish.)
How do I write down this problem in a format a solver can interpret. I've seen solvers which can take arithmetic expressions, but I haven't seen solvers that can do the sort of piecewise functions I have here.
If the above is too difficult, if I take a linear approximation of the problem, can this be translated efficiently (i.e. no exponential blowup) into something I can give a linear solver?
If even that is too difficult, can I solve the problem by iterating linear problems. An example Idea: start with the maximum efficiency slope, solve that, then adjust the slope depending on the result given then solve that. (This will probably not end up being optimal, but close enough.) Will this, or some other scheme, converge?
Thanks!
I'm still not clear on what is being summed in the objective -- the components of $A (f \circ x)$? -- but you can formulate the problem as a mixed integer linear program if you know bounds on $x.$
Assume that $x_i \in \lbrace 0,1,\dots,N_i \rbrace$ for each $i.$ Introduce binary variables $y_{i,j}$ for each $i$ and each $j\in \lbrace 0,1,\dots,N_i \rbrace$ with the constraints $$\sum_{j=0}^{N_i} y_{ij} = 1 \quad \forall i.$$ Also introduce continuous variables $z_i$ defined by the constraints $$z_i = \sum_{j=0}^{N_i} f(j) \cdot y_{ij} \quad \forall i.$$ We set $$x_i = \sum_{j=0}^{N_i} j\cdot y_{ij} \quad \forall i,$$ from which it follows that $z_i=f(x_i)$ and so $z = f \circ x.$ Now minimize the objective (expressed in terms of $z$ rather than $x$) subject to $Az \ge d$ plus the above constraints.