An external reconstruction approach (ERA) to linear programming (Q1099782): Difference between revisions

The linear programming problem under consideration consists in minimizing z subject to \[ \sum^{n}_{j=1}a_{ij}x_ j\leq b_ i,\quad i=1,...,m,\quad x_ j\geq 0,\quad j=1,...,n. \] Let us denote \(B^ 0=\sum^{m}_{i=1}b_ i\), \(A^ 0_ j=\sum^{m}_{i=1}a_{ij}\) and let \(P^ 0\) consist in minimizing z subject to \(\sum^{m}_{j=1}A^ 0_ jx_ j\leq B^ 0\), all \(x_ j\geq 0\). Let \(x^{*0}=(x_ 1^{*0},...,x_ n^{*0})\) be an optimum solution to \(P^ 0\). Furthermore, let \(P^ r\) (r\(\geq 1)\) consist in maximizing z subject to \[ \sum^{n}_{j=1}a_{sj}x_ j\leq b_ s,\quad s=0,1,...,r\quad (a_{0j}=b_ 0=0),\quad \sum^{n}_{j=1}A^ r_ jx_ j\leq B^ r,\quad all\quad x_ j\geq 0, \] where \(A^ r_ j=A_ j^{r-1}- a_{rj}\), \(B^ r=B^{r-1}-b_ r\). If \(x^{*r}=(x^ r_ 1,...,x^ r_ n)\) is an optimum solution to \(P^ r\) we check whether \(\sum^{n}_{j=1}a_{ij}x^*_ j\leq b_ i\) for \(i=1,...,n\). If not, we assume (to simplify notation) that \(b_{r+1}=\max \{b_ i| \sum^{n}_{j=1}a_{ij}x^*_ j>b_ i\}\), and form \(P^{r+1}\) by adding to \(P^ r\) the constraint \(\sum^{n}_{j=1}a_{r+1,j}\) \(x_ j\leq b_{r+1}\) and by replacing the last constraint of \(P^ r\) by \(\sum^{n}_{j=1}A_ j^{r+1}x_ j\leq B^{r+1}\). The method is illustrated on a small numerical example. Several potential uses and applications are listed.