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

頂点集合を $\{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)$ の最大値を求めよ。

頂点集合を $V=\{1,2,3,4,5,6,7\}$、辺集合を
$$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,1\}\}$$
とする閉路グラフ $C_7$ を考える。$C_7$ の最大安定集合問題の整数計画
$$(\mathrm{IP})\text{maximize}\sum _{v=1}^7{x}_v\text{subject to}{x}_u+x_v\le 1(\{u,v\}\in E),x_v\in \{0,1\}(v\in V)$$
の最適値を $z_{\mathrm{IP}}$ とし、$x_v\in \{0,1\}$ を $0\le x_v\le 1$ に置き換えた線形計画緩和 $(\mathrm{LP})$ の最適値を $z_{\mathrm{LP}}$ とする。$z_{\mathrm{LP}}-z_{\mathrm{IP}}$ を求めよ。

$E=\{1,2,3,4,5,6\}$ とし、$E$ 上の一様マトロイド $U_{3,6}$ を考える。すなわち、$E$ の部分集合 $I$ が独立であるとは $|I|\le 3$ であることとする。各要素 $i\in E$ に重み $w(i)$ を
$$w(1)=4,w(2)=7,w(3)=2,w(4)=7,w(5)=5,w(6)=3$$
で与え、基 $B$ の重みを $w(B)={\sum }_{i\in B}w(i)$ と定める。$U_{3,6}$ の基の重みの最大値を求めよ。

$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 })$ の最大値を求めよ。