プレプレスでLPを解く

Question

私は整数プログラミングモデルを持っています。私はそれをcplexで線形緩和したいと考えています。もともと、私は私として変数を定義していた：

BoolVarMatrix X(env,I); 
for(IloInt i = 0; i < I; i++){ 
    X[i] = IloBoolVarArray(env, J); 
} 

IloBoolVarArray y(env,J); 

が、今、私は0 < = X < = 1、0 < = Y < = 1の範囲にそれらを緩和すべきです。これを行うために、私は定義を次のように変更しました：

NumVarMatrix X(env,I, 0, 1); 
for(IloInt i = 0; i < I; i++){ 
    X[i] = IloNumVarArray(env, J, 0, 1); 
} 

IloNumVarArray y(env,J, 0, 1); 

しかし、それでも私には整数解決策が与えられます。私は代わりに何をすべきですか？

Answer 1

リラックスしたLPでも整数の最適解が得られる可能性は非常に高いです。 バインディングを追加することを確認する簡単な方法は、を部分的な値にすることです。

X1のlbとubを変更します。0 <= x1 <= 1とし、それを0.01 <= x1 <= 0.99にしてLPを解きます。元の処方でバイナリだったすべての変数に対してこれを行います。

つまり、小数であることを UBと IloNumVarArrayの ポンドを作り、あなたが最適なソリューションで分数の値を取得する場合、あなたは右の緩和を行っていることを知っています。

Answer 2

あなたの拘束係数行列A（AX = b）は単峰性であるかもしれません。

Answer 3

バイナリ変数をILOFLOATに変換する必要はありません。 LPRelaxのように、新しいモデルのインスタンスを定義し、以下のようにIloConversionを使用します。

IloModel LpRelax(env); 
LpRelax.add(model); 
LpRelax.add(IloConversion(env, vars, ILOFLOAT)); 

IloCplex cplex(env); 
cplex.extract(LpRelax); 
cplex.solve(); 

それでも整数解を得る場合は、あなたの問題は一体化することがあります。私は、あなたのcoefficinetが一体型RHSと一体的なソリューションを生産すると共に、TOTALY UNIMODULARITYのような特殊な特性を持っていることを意味します。

希望すると:-)。