embotech / ecos

A lightweight conic solver for second-order cone programming.
GNU General Public License v3.0
478 stars 123 forks source link

fixed condition to branch on infeasible node #174

Closed Isitar closed 5 years ago

Isitar commented 5 years ago

The current version of ecos_bb still tries to calculate split_idx and split_val on an infeasible node.

If the problem is infeasible there is no integer solution possible that is feasible and therefore there should be no branching on this node.

simple example to test:

C Code:

idxint n = 4;
idxint m = 4;
idxint p = 2;
idxint l = 4;
idxint nCones = 0;

// cost function
pfloat c[4] = { 0, 0, -10, -17 };

//cone
idxint Gjc[5] = { 0, 1, 2, 3, 4 };
idxint Gir[4] = { 0, 1, 2, 3 };
pfloat Gpr[4] = { -1.0, -1.0, -1.0, -1.0 };
pfloat h[4] = { 0.0, 0.0, 0.0, 0.0 };
idxint *q = NULL;

//lp matrix
idxint Ajc[5] = { 0, 1, 2, 4, 6 };
idxint Air[6] = { 0, 1, 0, 1, 0, 1 };
pfloat Apr[6] = { 1, 1, 1, 5, 1, 9 };
pfloat b[2] = { 12, 90 };
idxint num_bool = 0;
idxint *bool_idx = NULL;
idxint num_int = 2;
idxint int_idx[2] = { 2, 3 };
ecos_bb_pwork *ILPHS18; idxint exitFlag;
settings_bb * settings = get_default_ECOS_BB_settings();
ILPHS18 = ECOS_BB_setup(n, m, p, l, nCones, q, 0, Gpr, Gjc, Gir, Apr, Ajc, Air, c, h, b, num_bool, bool_idx, num_int, int_idx, settings);
exitFlag = ECOS_BB_solve(ILPHS18);
ECOS_BB_cleanup(ILPHS18, 0);

this problem is solvable with ~6 iterations of branching. The current version cannot solve (and prove) it in 1000 iterations.


This change is Reviewable

coveralls commented 5 years ago

Coverage Status

Coverage remained the same at ?% when pulling 6f32caa119425f3150f0fdd90191010ab85a658c on Isitar:bugfix/stop-branching-on-infeasible-node into fc6afa2b92e8e86f7a20556309d2332807b8985f on embotech:develop.

adomahidi commented 5 years ago

Thanks for providing this fix!