線形最適化—Wolfram Documentation

線形最適化

はじめに	線形最適化の応用例題
LinearOptimization関数	線形最適化のアルゴリズム
例題	参考文献
大きいデータをインポートし，大規模問題を解く

はじめに

線形最適化問題とは，目的関数と制約条件がすべて線形である問題を言う．

Wolfram言語には実数変数を持つ線形最適化問題を解くためのアルゴリズム群があり，LinearOptimization，FindMinimum，FindMaximum，NMinimize，NMaximize，Minimize，Maximizeでアクセスできる．LinearOptimizationを使うと，線形最適化アルゴリズムに直接アクセスできる．これは使用するメソッドを最も柔軟に指定することができ，大規模な問題に最も効率的である．FindMinimum，FindMaximum，NMinimize，NMaximize，Minimize，Maximizeは方程式および不等式の形式での線形最適化問題を解くのに便利である．

下の線形最適化問題

をMinimizeで解いてみる：

Wolfram Language code: Minimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]

次に，同じ問題をNMinimizeで解いてみる．NMinimizeは機械数の解を返す：

Wolfram Language code: NMinimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]

さらに同じ問題をLinearOptimizationで解く：

Wolfram Language code: LinearOptimization[x + 2y, {-5x + y == 7, x + y >= 26, x >= 3, y >= 4}, {x, y}]

LinearOptimization関数

LinearOptimization は線形最適化の主要関数であり，使用するメソッドの指定が最も柔軟にでき，大規模な問題に最も効率的である．

線形最適化は，以下の主問題を解くを求める：

	最小化する
	次の制約条件に従う
	ここで

線形最適化のラグランジュ双対問題は以下で与えられる：

	最大化する
	次の制約条件に従う
	ここで

以下のオプションを取ることができる．

オプション名	デフォルト値
Method	Automatic	線形最適化問題を解くのに使用するメソッド
Tolerance	Automatic	収束の許容誤差
MaxIterations	Automatic	使用する反復の最大回数
PerformanceGoal	$PerformanceGoal	最適化を試みる精度
WorkingPrecision	Automatic	内部計算で使用する精度

LinearOptimizationのオプション

Methodオプションは，線形最適化問題を解くアルゴリズムを指定する．これで使用できる値はAutomatic，"Simplex"，"RevisedSimplex"，"InteriorPoint"， "CLP"，"MOSEK"，"Gurobi"である．デフォルトはAutomaticであり，問題の大きさと精度に基づいて，他のメソッドの中から自動的に選ばれる．

Toleranceオプションは，収束の許容誤差を指定する．

WorkingPrecision->Automaticにすると，機械精度でしか動作しないメソッドが指定されていない限り，精度は入力引数の精度から自動的に取られる．そのメソッドが指定されている場合は機械精度が使われる．

LinearOptimizationからアクセスできる解の特性は多数ある：

"PrimalMinimizer"	{,…}	目的関数を最小化する変数値のリスト
"PrimalMinimizerRules"	{v₁,…}	を最小化する変数 vars={v₁,…}の値
"PrimalMinimizerVector"	x^*	を最小化するベクトル
"PrimalMinimumValue"		の最小値
"DualMaximizer"		を最大化するベクトル
"DualMaximumValue"		双対最大値
"DualityGap"		双対問題の最適値と主問題の最適値の差分（強双対性のため0）
"Slack"		制約条件緩和ベクトル
"ConstraintSensitivity"		制約条件摂動へのの敏感性
"ObjectiveVector"		線形目的ベクトル
"LinearInequalityConstraints"		線形不等式制約条件行列およびベクトル
"LinearEqualityConstraints"		線形等式制約条件行列およびベクトル
{"prop₁","prop₂",...}		いくつかの解の特性

LinearOptimizationの解の特性

例題

内点法とシンプレックス法および／または改訂シンプレックス法との違い

シンプレックス法および改定シンプレックス法は，極小値に達するまで目的関数の継続的に小さい方の値で頂点から頂点へと，制約条件により定義されたポリトープの辺に沿って移動することにより線形最適化問題を解く．これらの関数のWolfram言語の実装では，密な線形代数が使われる．この実装のユニークな点は，厳密・拡張精度問題が解けるという点である．したがって，これらの方法は，非機械数の結果が必要ない，または頂点の解が望まれるような小さいサイズの問題に適している．

線形最適化の内点法は，大まかに言うと，制約条件により定義されたポリトープの内部から反復する．これは非常に速く解に近付くが，シンプレックス・改訂シンプレックス法とは異なり，厳密な解は見付けない．Wolfram言語における内点法の実装では，機械精度の疎な線形代数を使う．よって，大規模の機械精度線形最適化問題では，内点法の方が効率がよいのでこれを使うべきである．

以下では，重解（{0,1}と{1,0}の間の線分上にある任意の点が解となる）を持つ線形最適化問題を解く．内点法では，解集合の中央にある解が返される：

Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "InteriorPoint"]

SimplexまたはRevisedSimplexを使うと，解集合の境界の解が返される：

Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "RevisedSimplex"]

以下は，200個の変数のランダムで疎な線形最適化問題では，内点法の方がずっと速く，同様な最適値を与えることを示している：

Wolfram Language code:

m = SparseArray[RandomChoice[{0.1, 0.9} -> {1., 0.}, {50, 200}]];
xi = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; //Timing

Wolfram Language code: xs = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "Simplex"]; //Timing

Wolfram Language code: Range[200].(xi - xs)

二重変数の探索

一般的な線形計最適化問題

がある場合，その双対問題は次の通りである．

両方の解が分かっていると便利な場合がある．

主問題と双対問題の解の関係は次の表の通りである．

主問題が…ならば	双対問題は…である
実行可能	実行可能
非有界	実行不可能または非有界
実行不可能	非有界または実行不可能

両方の問題が実行可能である場合，(P)と(D)の最適値は同じであり，主問題の解および双対問題の解に対して次の相補条件が成り立つ．

双対の最大化はLinearOptimizationで"DualMaximizer"特性を使うことで得ることができる．

次で主問題

の他に，下の双対問題も解く．

Wolfram Language code:

primal = LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimizerRules", "DualMaximizer"}]

双対問題を解いて，結果を確かめる：

Wolfram Language code:

dual = LinearOptimization[-(5Subscript[λ, 1] + Subscript[λ, 2] - 4Subscript[λ, 3] + Subscript[λ, 4] - 4Subscript[λ, 5]), {Subscript[λ, 1] + Subscript[λ, 2] - Subscript[λ, 3] == 3, 
	2Subscript[λ, 1] + Subscript[λ, 4] - Subscript[λ, 5] == 4, Subscript[λ, 1] >= 0, Subscript[λ, 2] >= 0, Subscript[λ, 3] >= 0, Subscript[λ, 4] >= 0, Subscript[λ, 5] >= 0}, {Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]}]

以下で主問題と双対が同じ目的値を与えることが確認できる：

Wolfram Language code: {3, 4}.{x, y} /. primal[[1]]

Wolfram Language code: {5, 1, -4, 1, -4}.{Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]} /. dual

主問題と双対問題の目的値を，解の特性を使って直接確認する：

Wolfram Language code: LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimumValue", "DualMaximumValue"}]

この制約条件

の双対は

である．これは，制約条件の右辺が1単位増加すると，最適値は2単位増加することを意味している．このことは，制約条件の右辺を0.001で摂動させることで確認できる：

Wolfram Language code: pval = LinearOptimization[3x + 4y, {x + 2y >= 5 + 0.001, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, "PrimalMinimumValue"]

以下の通り，目的値はその倍増加している：

Wolfram Language code: pval - {3, 4}.{x, y} /. primal[[1]]

"ConstraintSensitivity"特性を使って，制約条件

に対する摂動

の影響を見る：

Wolfram Language code:

{a, b} = {{{1, 2}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}, {-5, -1, 4, -1, 4}};
{p^ * , {Subscript[s, λ], Subscript[s, ν]}} = LinearOptimization[3x + 4y, a.{x, y} + b0, {x, y}, {"PrimalMinimumValue", "ConstraintSensitivity"}]

Wolfram Language code: p^ * + Subscript[s, λ].{-0.001, 0, 0, 0, 0}

内点法における実行不可能性と非有界性の扱い

主双対内点法は実行可能な問題に対して設計されており，実行不可能／非有界の問題では発散してしまう．その上，現在の実装では発散が実行不可能性によるものか非有界性によるものかを見分けるのは難しい．

ヒューリスティックが実行不可能／非有界の問題を見付け，適切なメッセージを出力する：

Wolfram Language code: LinearOptimization[x + y, {x + y <= 1, x + y >= 2}, {x, y}, Method -> "InteriorPoint"]

ヒューリスティックを使っても，問題が実行不可能／非有界のどちらであるかを確実に見分けることができない場合がある：

Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "InteriorPoint"]

Simplexを使うと問題が非有界であることが分かる：

Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "Simplex"]

"InteriorPoint"のメソッドオプション

"TreatDenseColumn"は"InteriorPoint"のメソッドオプションであり，密な列を別々に扱うかどうかを決定する．密な列とは，多くの非零要素を含む制約行列の列のことである．このメソッドのデフォルト値はAutomaticであり，密な列は別々に扱われる．

密な行列を含む大きな問題では特にこのメソッドが便利である：

Wolfram Language code:

A = SparseArray[{{i_, i_} -> 1., {i_, 1} -> 1.}, {300, 300}];
c = Table[1, {300}];
b = A.Range[300];

Wolfram Language code:

{x1 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; // Timing, 
	x2 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> {"InteriorPoint", "TreatDenseColumns" -> False}];//Timing}

Wolfram Language code: x1.c - x2.c

大きいデータをインポートし，大規模問題を解く

線形最適化問題を記述するのによく使われる形式はMPS（数理計画問題）形式である．これは多数のセクションで構成されるテキスト形式である．

方程式のMPSファイルをインポートする

Wolfram言語はMPS形式のファイルをインポートすることができる．MPSデータのImportにより，線形最適化問題はデフォルトで方程式形式で返される．この形式はLinearOptimization，Minimize，NMinimizeを使って解くことができる．

次でMPSファイル"afiro.mps"で指定された線形最適化問題を解く：

Wolfram Language code: {eqns, vars} = Import["Optimization/Data/afiro.mps"]

Wolfram Language code: LinearOptimization[eqns[[1]], Rest[eqns], vars]

大規模な問題：行列形式およびベクトル形式でのインポート

大規模な問題の場合，MPSデータファイルをインポートし，行列かベクトルで行列問題を表してからLinearOptimizationを使って解いた方が効率的である．

次で，MPS形式のデータで3つの要素がインポートできることを示す：

Wolfram Language code: Import["Optimization/Data/ganges.mps", "Elements"]

以下で，1309の制約条件と1681の変数を持つ問題"ganges"をインポートする：

Wolfram Language code: {c, linIneq, linEq} = Import["Optimization/Data/ganges.mps", "LinearOptimizationData"];

問題を解き，最適値を見付ける：

Wolfram Language code: x = LinearOptimization[c, linIneq, linEq];

Wolfram Language code: c.x

疎な制約行列だけを求めるときは"ConstraintMatrix"指定を使うことができる：

Wolfram Language code: p = Import["Optimization/Data/ganges.mps", "ConstraintMatrix"]

自由書式のMPSファイル

標準的なMPS形式のファイルでは固定書式が使われており，各欄の文字の位置が厳密に決まっている．しかし，モデリングシステムの中には自由書式のMPSファイルを出力するものもあり，欄の位置が自由である．後者のファイルでは，Importでオプション"FreeFormat"->Trueを指定することができる．

次の文字列は，MPSファイルを自由形式で記述している：

Wolfram Language code:

txt = "NAME TESTPROB
ROWS
 N COST
 L CON1
 G CON2
 E CON3 
COLUMNS
 x COST 1 CON1 2
 x CON2 3
 y COST 4 CON1 5
 y CON3 6
 Z COST 7 CON2 8
 Z CON3 9
RHS
 RHS1 CON1 10 CON2 11
 RHS1 CON3 12
BOUNDS
 UP BND1 x 13
 LO BND1 y 14
 UP BND1 y 15
ENDATA
";

一時的ファイル名を割り当て，それに文字列をエキスポートする：

Wolfram Language code:

file = Close[OpenWrite[]];
Export[file, txt, "Text"];

オプション"FreeFormat"->Trueを使ってファイルをインポートする：

Wolfram Language code: Import[file, "MPS", "FreeFormat" -> True]

線形最適化テスト問題

NetLib線形最適化テスト問題はすべてExampleData関数からアクセスすることができる．

Netlib集合のすべての問題を見付ける：

Wolfram Language code: ExampleData["LinearOptimization"]

問題"afiro"をインポートし，それを解く：

Wolfram Language code: afiroData = ExampleData[{"LinearOptimization", "afiro"}]

Wolfram Language code: LinearOptimization@@afiroData

"afiro"問題に対してインポートすることのできる他の特性を表示する：

Wolfram Language code: ExampleData[{"LinearOptimization", "afiro"}, "Properties"]

"afiro"を方程式形式でインポートする：

Wolfram Language code: afiroEqns = ExampleData[{"LinearOptimization", "afiro"}, "Equations"]

Wolfram Language code: LinearOptimization[Sequence@@afiroEqns[[1]], afiroEqns[[2]]]

線形最適化の応用例題

L1ノルム最小化

最小化問題

を，線形最適化問題に変換して解くことができる．

入力と出力の点を定義する：

Wolfram Language code:

{input, output} = IconizedObject[«Block»];
dataplot = ListPlot[output, PlotRange -> All]

以下がデータにフィットする：

Wolfram Language code:

Clear[a, b, s, x];
res = LinearOptimization[Total[s], {a == input, b == output, -sa.x - bs}, {x, s}]

以下で直線をプロットし，外れ値についてロバストであることを示す：

Wolfram Language code: Show[ dataplot, Plot[Evaluate[x.{1, t} /. res], {t, 1, 30}]]

LeastSquaresを使って得られたフィットと比較する：

Wolfram Language code: line = Fit[output, {1, t}, t]

Wolfram Language code: Show[ dataplot, Plot[Evaluate[{x.{1, t} /. res, line}], {t, 1, 30}]]

最適なトラスの設計

この例題は[2]から採用したものである．この問題の目的は，負荷をサポートするのにできるだけ少ない材料を使ってアンカーを設計するというものである．

この問題は，まずノードとリンクを使って離散化し，シミュレーションを行うことによりモデル化することができる．モデル化の過程は以下の図で示す．ここで7×10のノードを持つ格子が生成される．それぞれのノードはマンハッタン距離が3以下である他のすべてのノードへのリンクにより接続される．赤い3つのノードは壁に固定されるもので，他のノードはすべて圧縮力および張力のバランスが取れていなければならない．

各リンクは厚みのある硬い棒を表しており，重さはそれにかかる力と長さに比例している．目標は，使用される材料を最小化することである．

したがって，これは数学的に線形の制約付き最小化問題であり，目的関数が線形関数の絶対値の和である．

目的関数の絶対値は，を圧縮力と張力（ともに非負）に分けて置き換えることができる．ここでをリンクの集合，をノードの集合，をノードとの間のリンクの長さ，とをそれぞれリンク上の圧縮力と張力とすると，上記のモデルは下の線形最適化問題に変換することができる．

トラスが壁に固定されているいくつかの位置を選ぶ．

Wolfram Language code: anchorPoints = Thread[{0, Range[-3, 3]}];

負荷がかかる位置はトラスの端である．

Wolfram Language code: forcingPoint = {30, 0};

トラスはリンクとノードを使ってモデル化することができる．各ノードはリンクによって近隣のノードに接続される．接続パターンは以下で与えられる．

Wolfram Language code:

connectivityPattern = Partition[Flatten[{Thread[{{-1, 1}, 0}], Outer[List, Range[-3, 3], {-1, 1}], Outer[List, {-3, -1, 1, 3}, {-2, 2}], Outer[List, {-2, -1, 1, 2}, {-3, 3}]}], 2];

候補のノードは矩形格子に置かれる．

Wolfram Language code:

bounds = {{0, 30}, {-10, 10}};
nodes   = Flatten[Outer[List, Sequence@@Apply[Range, bounds, 1]], 1];
np = Length[nodes];

ノードの位置，アンカーの位置，力が加わる位置，トラスの中央の単独のノードの接続性を可視化する．

Wolfram Language code:

mid  = Round[Map[Mean, bounds]];
cmid = Map[Plus[mid, #]&, connectivityPattern];
Graphics[{Point[nodes], Blue, Map[Circle[#, .5]&, anchorPoints], Red, Arrow[{forcingPoint, forcingPoint - {0, 2}}], Map[Line[{mid, #}]&, cmid]}, ImageSize -> Medium]

各ノードは一意の指標に関連付けられている．Associationを使うことで迅速にルックアップテーブルが提供される．

Wolfram Language code:

toIndex = AssociationThread[nodes -> Range[np]];
fromIndex = AssociationThread[Range[np] -> nodes];

アンカーおよび力が加わる点に関連付けられた指標を求める：

Wolfram Language code:

anchorPointIndex = Lookup[toIndex, anchorPoints];
forcePointIndex   = toIndex[forcingPoint];

指定された接続パターンに対する格子点の接続性を求める関数を構築する．

Wolfram Language code:

connectivity[index_, pat_] := Module[{point = fromIndex[index], connectedPoints, connectedIndexes}, 
	connectedPoints  = Map[Plus[point, #]&, pat];
	connectedIndexes = Cases[Map[toIndex, connectedPoints], Except[_Missing]];
	Thread[{index, Sort[connectedIndexes]}]];

リンクの集合を

で記述する．リンクが

ならば

でそれ以外は

であるという，先ほど定義されたパターンを使って，ノードに対する疎な接続行列

を定義する．

Wolfram Language code:

nodePosition = Join@@Map[connectivity[#,   connectivityPattern]&, Range[np]];
nodeConnectivityMatrix = SparseArray[nodePosition -> 1, {np, np}]

Wolfram Language code:

links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]];
nlinks = Length[links];

のリンクを記述するには，リンクの指標を使うと便利である．

Wolfram Language code: linkToIndex = AssociationThread[links -> Range[nlinks]];

目的は，

を最小化することである．ここで

はノード

と

の間の長さ，

は最終の接続点で

によって形成されるリンクから働く力である．

Wolfram Language code:

links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]];
nlinks = Length[links];
linkLengths = Map[EuclideanDistance@@nodes[[#]]&, links];

関数

は非線形であるが，

および

となるような

を導入することによって線形関数として表すことができる．目的は以下になる：

Wolfram Language code: objective = linkLengths.(xp + xm);

力を受ける点以外の各ノードでは，外部の力は受けない．

Wolfram Language code: nodeForce = ConstantArray[0., {np, 2}];

力を受ける点では，垂直の下向きの単位力が適用される．

Wolfram Language code: nodeForce[[forcePointIndex]] = {0., -1.};

固定されていないそれぞれのノードでは，力の均衡

がある．ここで

はノード

の位置である．

Wolfram Language code:

columns = nodeConnectivityMatrix["MatrixColumns"];
linkToIndex = AssociationThread[links -> Range[nlinks]];
linkConstraints = Table[
	mi = columns[[i]];
	vii = Map[Sort, Thread[{i, mi}]];
	vi = Map[Indexed[xp, linkToIndex[#]] - Indexed[xm, linkToIndex[#]]&, vii];
	s = Map[(nodes[[#]] - nodes[[i]])&, mi];
	lhs = Total[Map[# / Norm[#]&, s] * vi];
	Thread[lhs == nodeForce[[i]]]
	, {i, Complement[Range[np], anchorPointIndex]}];

最終的な制約条件は以下になる．

Wolfram Language code: constraints = Join[Flatten[linkConstraints], {xp0, xm0}];

結果の系を解く．

Wolfram Language code:

res = LinearOptimization[objective, constraints, {xp∈Vectors[nlinks], 
	xm∈Vectors[nlinks]}];

青がリンクの圧縮を示し，赤がリンクの拡張を示す最適トラスを可視化する．

Wolfram Language code:

totalf = (xp - xm) /. res;
maxForce = Max[Abs[totalf]];
index = Pick[Range[nlinks], Thread[Abs[totalf] / maxForce ≥ 0.001], True];
allLinks = Table[
	f = totalf[[i]] / maxForce;
	vlink = nodes[[links[[i]]]];
	{Hue[(1 + f) / 2.5], Thickness[.025 Abs[f]], Line[vlink]}, 
	{i, index}];
Graphics[{allLinks, {PointSize[0.02], Point[anchorPoints]}, {EdgeForm[StandardGray], FaceForm[None], Rectangle[{-1, -10}, {0.01, 10}]}}, ImageSize -> Medium]

線形最適化のアルゴリズム

シンプレックス法と改訂シンプレックス法

シンプレックス法と改訂シンプレックス法は，制約条件により定義された多面体の頂点で実行可能解を構築し，その後目的関数のより小さな値を連続的に使い，最小値に達するまでその多面体の辺を頂点に向かって移動させていくことにより最適化問題を解く．

シンプレックス法と改訂シンプレックス法の実装が少ないと実際に非常に効率的であり，大域的最適値が見付かることが保障されているが，最悪の場合には動作に問題が生じる場合もある．構築された線形最適化問題に対して，シンプレックス法と改訂シンプレックス法がその問題の大きさに指数関数的な数のステップを取らなければならなくなる可能性があるのである．

Wolfram言語は密な線形代数を使ってシンプレックス法と改訂シンプレックス法を実装する．この実装のユニークな点は，厳密・拡張精度問題が解けるという点である．従って，これらのメソッドは機械数でない結果が必要とされる小さい問題により適している．

以下で20の制約条件と200個の変数を持つランダムな線形最適化問題を設定する：

Wolfram Language code:

SeedRandom[123];
{m, n} = {20, 100};
c = RandomInteger[{1, 10}, n];
A = RandomInteger[{-100, 100}, {m, n}];
b = A.ConstantArray[1, n];
constraints = {A.xb, -10x10};

この問題を解く．制約条件の数よりも変数の数の方がかなり多い線形最適化問題では，通常改訂シンプレックス法の方が早い．これに反して，変数よりも制約条件の数のほうが多い場合は，シンプレックス法の方が速い：

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "Simplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "RevisedSimplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]

機械数の結果だけが必要な場合は，問題を機械数の問題に変換し，内点法を使わなければならない：

Wolfram Language code:

t = Timing[res = LinearOptimization[c.x, constraints, x, 
	"PrimalMinimizerVector", Method -> "InteriorPoint"];];
Print["time = ", t[[1]], " optimal value = ", c.res]