凸最適化・組合せ最適化の問題

頂点集合を $\{1,2,3,4\}$ とする完全グラフ $K_4$ の辺集合を $E$ とし、$M$ を $E$ 上のグラフ的マトロイド（独立集合は森をなす辺集合）、$M^{\ast }$ をその双対マトロイドとする。各辺 $e\in E$ に重み $w(e)$ を
$$w(\{1,2\})=1,w(\{1,3\})=4,w(\{1,4\})=3,w(\{2,3\})=2,w(\{2,4\})=6,w(\{3,4\})=5$$
で与え、辺集合 $B$ の重みを $w(B)={\sum }_{e\in B}w(e)$ と定める。$M^{\ast }$ の基の重みの最大値を求めよ。

有限集合 $E=\{1,2,3,4,5,6,7,8\}$ の部分集合の族 $(A_1,A_2,A_3,A_4,A_5)$ を次で定める。
$$A_1=\{1,2\},A_2=\{1,2\},A_3=\{1,3,4\},A_4=\{3,4,5\},A_5=\{5,6,7,8\}.$$
部分集合 $I\subseteq E$ が独立であるとは、単射 $\phi :I\to \{1,2,3,4,5\}$ で、すべての $i\in I$ に対して $i\in A_{\phi (i)}$ を満たすものが存在することと定める（$\phi$ は空写像でもよく、$\varnothing$ は独立とする）。このとき独立集合全体は $E$ 上のマトロイド $M$（族 $(A_1,\dots ,A_5)$ の横断マトロイド）をなす。

各要素の重み $w:E\to \mathbb{R}$ を
$$w(1)=6,w(2)=5,w(3)=8,w(4)=7,w(5)=10,w(6)=9,w(7)=4,w(8)=3$$
とし、$B\subseteq E$ に対して $w(B)={\sum }_{i\in B}w(i)$ とおく。$M$ の基 $B$ に対する $w(B)$ の最大値を求めよ。

$E=\{1,2,3,4,5,6,7\}$ とし、各 $i\in E$ に ${\mathbb{R}}^3$ のベクトル $v_i$ を次のように対応させる。
$$v_1=(1,0,0),v_2=(0,1,0),v_3=(1,1,0),v_4=(0,0,1),v_5=(1,0,1),v_6=(2,2,0),v_7=(1,1,1)$$
$M$ を $E$ 上の線形マトロイド（$I\subseteq E$ が独立であるとは、$\{v_i{\}}_{i\in I}$ が $\mathbb{R}$ 上一次独立であること）とし、$M^{\ast }$ をその双対マトロイド（基は $M$ の基の補集合）とする。各要素の重みを
$$w_1=9,w_2=8,w_3=10,w_4=4,w_5=7,w_6=6,w_7=5$$
と定め、部分集合 $B$ の重みを $w(B)={\sum }_{i\in B}{w}_i$ とする。$M^{\ast }$ の基 $B^{\ast }$ にわたる $w(B^{\ast })$ の最大値を求めよ。

頂点集合を $V=\{1,2,3,4,5,6\}$ とし、辺集合 $E=\{e_1,e_2,e_3,e_4,e_5,e_6\}$ を
$$e_1=\{1,2\},e_2=\{2,3\},e_3=\{1,3\},e_4=\{4,5\},e_5=\{5,6\},e_6=\{3,4\}$$
とするグラフ $G=(V,E)$ を考える。$M(G)$ を $E$ 上のグラフ的マトロイド（辺の部分集合が独立であるとは、それが閉路を含まないこととする）とし、$r$ をその階数関数とする。$X=\{e_1,e_2,e_3,e_4,e_5\}$ に対して $r(X)$ を求めよ。

${\mathcal{S}}^4$ を $4$ 次実対称行列全体とし、$A,B\in {\mathcal{S}}^4$ に対して $⟨A,B⟩=\mathrm{tr}(AB)={\sum }_{i,j}{A}_{ij}{B}_{ij}$ と定める。$X⪰O$ は $X$ が半正定値であることを表す。行列 $C\in {\mathcal{S}}^4$ を
$$C=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$$
とし、$X=(X_{ij})\in {\mathcal{S}}^4$ を変数とする次の半正定値計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}⟨C,X⟩\text{subject to}{X}_{ii}=1(i=1,2,3,4),X⪰O$$
$(\mathrm{P})$ の最適値を求めよ。