scientific article; zbMATH DE number 3906236

From MaRDI portal
Publication:3683899





The following problem P is considered: (1.1) \(\sum_{j\in I}c_ jx_ j\to \max\), (1.2) \(\sum_{j\in I}a_ jx_ j\leq b\), (1.3) \(\sum_{j\in G_ i}x_ j=1\) \((i=1,...,q)\), (1.4) \(x_ j\leq 1\) (j\(\in K)\), (1.5) \(x_ j\geq 0\) (j\(\in I)\), (1.6) \(x_ j\leq U_ j\) (j\(\in R)\), (1.7) \(x_ j\) integer (j\(\in G\cup K)\), where \(I=\{1,...,n\}\), \(\cup^{q}_{i=1}G_ i=G\subseteq I\), \(K\subseteq I\), \(R\subseteq I\), the sets \(G_ i\) \((i=1,...,q)\), K and R are mutually exclusive. The paper presents some important properties of optimal solutions to problem P and to its linear relaxation LP, gives a solution method for the problem LP and for the approximate solution of problem P, and a procedure for an a priori analysis to reduce the dimension. As conclusion a computationally efficient multistage solution procedure is outlined: (1.) Problem P is solved for an approximate solution, which gives a lower bound to the optimal value of the criterion. (2.) Problem LP is solved (analytically). (3.) The procedure for the a priori analysis of problem P is applied. This includes solution of LP (\(| G|\) times) under additional assumption \(x_ j=\alpha\), where \(j\in G\), \(\alpha\in \{0,1\}\) and for each j the value of \(\alpha\) is defined from the solution of step 2. As a result the optimal values of a part of the binary variables are determined and the dimension of problem P is reduced. (4.) The reduced problem P is solved by means of a dynamic programming algorithm.




Cited in
(26)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683899)