An external reconstruction approach (ERA) to linear programming (Q1099782): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0305-0548(86)90067-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968479760 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonadjacent extreme point methods for solving linear programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3716769 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3347650 / rank | |||
Normal rank |
Latest revision as of 16:21, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An external reconstruction approach (ERA) to linear programming |
scientific article |
Statements
An external reconstruction approach (ERA) to linear programming (English)
0 references
1986
0 references
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.
0 references
nonsimplex ways
0 references
externally initiated optimum-searching procedure
0 references
external reconstruction approach
0 references