We formulate the research problems which are a generalization of our
earlier results in the field of intractable combinatorial optimization problems. On the
basis of these problems, we have created a hierarchical model of planning and
decision making for objects with a network representation of technological processes and limited resources (Chap. 9). We say that the problem is intractable if it is NP-hard (NP-hard in the strong sense) or such for which an exact polynomial time solution algorithm has not been yet obtained. To solve such problems efficiently,
we developed a methodology of PSC-algorithms construction meaning the algorithms which necessarily include the following: sufficient conditions (signs) of a feasible solution optimality, verification of which can be implemented only at the stage of a feasible solution construction by a polynomial algorithm (the first
polynomial component of the PSC-algorithm). The second polynomial component
of the PSC-algorithm is an approximation algorithm with polynomial complexity.
For NP-hard (NP-hard in the strong sense) combinatorial optimization problems, a
PSC-algorithm may include an exact algorithm for its solving in case if sufficient
conditions were found, satisfying of which during this algorithm execution turns it
into a polynomial complexity algorithm (Chaps. 4 and 5). We also give a brief
overview of the monograph’s chapters content.