  A combinatorial optimization problem (COP) has a finite groundset
$E(\left|E\right|=N$), a weight vector $c=\left(c^e:e\in E\right)$ and a family
$T\in E$ of feasible subsets with objective to find $t\in T$ with maximal
weight: ${max}\{\sum_{e\in t}c^e$: $t\in T\}$. Polyhedral combinatorics
reformulates combinatorial optimization as linear program: $T$ is mapped into
the set $X\in R^N$ of 0/1 incidence vectors and $c\in R^N$ is maximized over
the convex hull of $X$: ${max}\{cx: x\in conv(X)\}$. In theory, complementary
slackness conditions for the induced linear program provide optimality
conditions for the COP. However, in general case, optimality conditions for
combinatorial optimization have not been formulated analytically as for many
problems complete description of the induced polytopes is available only as a
convex hull of extreme points rather than a system of linear inequalities.
Here, we formulate optimality conditions for a COP in general case: $x_k\in X\
\ $is optimal if and only if $c\in cone\left(H_k\right)\ $ where $H_k$ $=\{h\in
V:\ {hx}_k\ \ge hx$ for all $x\in X\}$ and $V$ is the set of all -1/0/1 valued
vectors in $R^N$. This provides basis to get, in theory, a complete description
of a combinatorial polytope induced by any COP: all facet inducing inequalities
for $conv(X)$ can be written as $hx\le l$ where $h\in V$ and $l$ is integer. A
vector $h\in V$ induces a nonredundent facet if and only if $h\in H_k^o$ $\in
H_k$ for at least one $x_k\in X\ $(where $H_k^o$$=\{h\in H_k:h\notin
cone(H_k\setminus \{h\})\}$ ) and $l=\ $ $x_kh$.
