3-valued problem and reduction of some integer programming problems (Q1191882)

We are concerned with the following four types of integer problems. (1) Integer Selection Problem (ISP): Let \(n\), \(k\), \(m_ 1,\dots,m_ k\) be positive integers and let \(a^ r_{ij}\), \(b^ r_ j\), \(c_ j\), \(1\leq i\leq m_ r\), \(1\leq r\leq k\), \(1\leq j\leq n\) and \(z\) be given integers. Find an integer \(r\) with \(1\leq r\leq k\) and non-negative integers \(x_ 1,\dots,x_ n\) satisfying \(\sum^ n_{j=1} c_ j x_ j=z\) and \(\sum^ n_{j=1} a^ r_{ij} x_ j\leq b^ r_ i\) for \(1\leq i\leq m_ r\). (2) 3-valued Problem: Given integers \(a_{ij}\in\{-1,0,1\}\) and \(b_ i\), \(1\leq i\leq m\), \(1\leq j\leq n\), find \(x_ 1,\dots,x_ n\in \{0,1\}\) satisfying \(\sum^ n_{j=1} a_{ij} x_ j\leq b_ i\), \(i=1,\dots,m\). (3) Indeterminate Coefficient Problem (IDCP): Let \(m\), \(n\), \(p\) and \(q\) be positive integers, \(a_{ij}\), \(b_ i\), \(1\leq i\leq m\), \(1\leq j\leq n\) integers, and let \(g_{si}\), \(d_{jt}\in\{-1,0,1\}\) and \(\ell_{st}\), \(1\leq s\leq p\), \(1\leq t\leq q\) be given integers. Find non-negative integers \(x_ j\) and \(y_{ij}\in\{0,1\}\) satisfying \(\sum^ n_{j=1} a_{ij} y_{ij} x_ j\leq b_ i\), \(i=1,\dots,m\) and \(\sum^ m_{i=1}\sum^ n_{j=1} g_{si}y_{ij} d_{jt}\leq\ell_{st}\), \(s=1,\dots,p\), \(t=1,\dots,q\). (4) IDCP with boundedness conditions: Given integers \(u_ j\geq 0\), \(1\leq j\leq n\), solve the IDCP under the boundedness conditions \(x_ j\leq u_ j\), \(j=1,\dots,n\). The main objective is to show that the two problems ISP and IDCP are equivalent, and that any IDCP with boundedness conditions can be reduced to a 3-valued problem, as stated below: Any solution of a given ISP (resp. IDCP and IDCP with boundedness conditions) is derived from the solutions of the associated IDCP (resp. ISP and 3-valued problem) and vice versa. In order to state the second result on the 3-valued problem for given integers \(a_{ij}\in\{-1,0,1\}\) and \(b_ i\), \(1\leq i\leq m\), \(1\leq j\leq n\), we introduce two notions: We say that a subset \(J'\) of \(J=\{1,\dots,n\}\) is weakly (resp. strongly) removable, if for each \(j\in J'\) there exists \(i\in\{1,\dots,m\}\) satisfying \(a_{ij}\geq 0\) (resp. \(a_{ij}=1\)) and \(\sum_{h\in J-J'} a_{ih}>b_ i-a_{ij}\); and we say that \(J'\) is maximal if \(J'\cup\{k\}\) for any \(k\in J-J'\) is not weakly (resp. strongly) removable. Using the above terminologies, we may state the following result which provides useful necessary conditions for the existence of solutions of 3-valued problems: Let \(x_ 1,\dots,x_ n\) be a solution of the 3-valued problem formulated for \(a_{ij}\) and \(b_ j\). (i) If there are no solutions \(y_ 1,\dots,y_ n\in\{0,1\}\) such that \(\{j| y_ j=1\}=\{j| x_ j=1\}\cup\{k\}\) for \(k\) with \(x_ k=0\), then the subset \(\{j| x_ j=0\}\) is maximal as a weakly removable set and also maximal as a strongly removable set. (ii) If \(b_ i<0\) for any \(i\) and the inequality \(\sum_{j\in J_ --J'}\sum^ m_{i=1} a_{ij}>\sum^ m_{i=1} b_ i\), \(J_ -=\{j|\sum^ m_{i=1} a_{ij}<0\}\) holds for a subset \(J'\) of \(\{1,\dots,n\}\), then \(x_ j=1\) for some \(j\in J'\).