Erroneous constraint matrix after adding rows and columns

[uhrm]

Executing below program produces an erroneous LP with objective value 0.9.

Commenting in line 50 (to write out TST_DBG_0.mps) produces the expected LP with objective value 9.0.

The problem seems to be that after adding the Z columns (epigraph variables), the row CVX still has only zero coefficients. In this case, the coefficients of the final row CUT are mistakenly added to row CVX.

#include <math.h>
#include <stdbool.h>
#include <stdio.h>

#include <Clp_C_Interface.h>

int main(int argc, char *argv[]) {
	
	int m = 1;
	int n = 10;
	char buf[10];

	Clp_Simplex *mod = Clp_newModel();
	
	Clp_setLogLevel(mod, 2);

	Clp_resize(mod, 2*n+m, 0);

	// epigraph constraints (over)
	for (int j=0; j<n; j++) {
		Clp_rowLower(mod)[j] = -0.1;
		Clp_rowUpper(mod)[j] = INFINITY;
		snprintf(buf, 10, "O(%00d)", j);
		Clp_setRowName(mod, j, buf);
	}
	// epigraph constraints (under)
	for (int j=0; j<n; j++) {
		Clp_rowLower(mod)[n+j] = 0.1;
		Clp_rowUpper(mod)[n+j] = INFINITY;
		snprintf(buf, 10, "U(%00d)", j);
		Clp_setRowName(mod, n+j, buf);
	}
	// convexity constraint
	Clp_rowLower(mod)[2*n] = 1.0;
	Clp_rowUpper(mod)[2*n] = 1.0;
	Clp_setRowName(mod, 2*n, "CVX");
	// epigraph variables
	for (int j=0; j<n; j++) {
		double zlb = -INFINITY;
		double zub = INFINITY;
		double zobj = 1.0;
		int zofs[2] = { 0, 2 };
		int zidx[2] = { j, n+j };
		double zval[2] = { 1.0, 1.0 };
		Clp_addColumns(mod, 1, &zlb, &zub, &zobj, zofs, zidx, zval);
		snprintf(buf, 10, "Z(%00d)", j);
		Clp_setColumnName(mod, j, buf);
	}
	
	//Clp_writeMps(mod, "TST_DBG_0.mps", 0, 1, 1.0);
	
	// cut
	double clb = 0.5;
	double cub = INFINITY;
	int cofs[2] = { 0, 3 };
	int cidx[3] =    {   3,   5,   7 };
	double cval[3] = { 1.0, 1.0, 1.0 };
	Clp_addRows(mod, 1, &clb, &cub, cofs, cidx, cval);
	Clp_setRowName(mod, 2*n+m, "CUT");
	
	//Clp_writeMps(mod, "TST_DBG_1.mps", 0, 1, 1.0);
	
	// column
	double llb = 0.0;
	double lub = INFINITY;
	double lobj = 0.0;
	int lofs[2] = { 0, 21 };
	int lidx[21] = {
		   0,    1,    2,    3,    4,    5,    6,    7,    8,    9,
		  10,   11,   12,   13,   14,   15,   16,   17,   18,   19,
		  20
	};
	double lval[21] = {
		-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
		 1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,
		 1.0
	};
	Clp_addColumns(mod, 1, &llb, &lub, &lobj, lofs, lidx, lval);
	Clp_setColumnName(mod, n, "COL");
	
	//Clp_writeMps(mod, "TST_DBG_2.mps", 0, 1, 1.0);
	
	Clp_initialSolve(mod);
	
	printf("*** model status: ");
	switch (Clp_status(mod)) {
		case 0:
			printf("optimal\n");
			break;
		case 1:
		case 2:
			printf("infeasible\n");
			break;
		default:
			printf("unknown\n");
			break;
	}
	printf("*** objective value: %.4f\n", Clp_objectiveValue(mod));
	printf("*** solution:\n");
	for (int j=0; j<n+1; j++) {
		Clp_columnName(mod, j, buf);
		printf("***   %s: %.3f\n", buf, Clp_primalColumnSolution(mod)[j]);
	}
	
	Clp_deleteModel(mod);
}

[jjhforrest]

It is a bug due to a disconnect between CoinPackedMatrix and ClpModel. A CoinPackedMatrix stores its dimensions - rows and columns. These can be more than the number of rows and columns in ClpModel - this is deliberate. However it may compute these dimensions and so before the last addRows, the matrix only had 19 rows not 20 so that row went in the wrong place. Then the addColumns did put an entry but it was out of sync. One side effect of the writeMps was to synchronize the number of rows. A fix will go in soon. John Forrest

…

On 01/09/2019 20:01, uhrm wrote: Executing below program produces an erroneous LP with objective value 0.9. Commenting in line 50 (to write out |TST_DBG_0.mps|) produces the expected LP with objective value 9.0. The problem seems to be that after adding the |Z| columns (epigraph variables), the row |CVX| still has only zero coefficients. In this case, the coefficients of the final row |CUT| are mistakenly added to row |CVX|. #include <math.h> #include <stdbool.h> #include <stdio.h> #include <Clp_C_Interface.h> int main(int argc,char *argv[]) { int m =1; int n =10; char buf[10]; Clp_Simplex *mod =Clp_newModel(); Clp_setLogLevel(mod,2); Clp_resize(mod,2*n+m,0); // epigraph constraints (over) for (int j=0; j<n; j++) { Clp_rowLower(mod)[j] = -0.1; Clp_rowUpper(mod)[j] = INFINITY; snprintf(buf,10,"O(%00d)", j); Clp_setRowName(mod, j, buf); } // epigraph constraints (under) for (int j=0; j<n; j++) { Clp_rowLower(mod)[n+j] =0.1; Clp_rowUpper(mod)[n+j] = INFINITY; snprintf(buf,10,"U(%00d)", j); Clp_setRowName(mod, n+j, buf); } // convexity constraint Clp_rowLower(mod)[2*n] =1.0; Clp_rowUpper(mod)[2*n] =1.0; Clp_setRowName(mod,2*n,"CVX"); // epigraph variables for (int j=0; j<n; j++) { double zlb = -INFINITY; double zub = INFINITY; double zobj =1.0; int zofs[2] = {0,2 }; int zidx[2] = { j, n+j }; double zval[2] = {1.0,1.0 }; Clp_addColumns(mod,1, &zlb, &zub, &zobj, zofs, zidx, zval); snprintf(buf,10,"Z(%00d)", j); Clp_setColumnName(mod, j, buf); } //Clp_writeMps(mod, "TST_DBG_0.mps", 0, 1, 1.0); // cut double clb =0.5; double cub = INFINITY; int cofs[2] = {0,3 }; int cidx[3] = {3,5,7 }; double cval[3] = {1.0,1.0,1.0 }; Clp_addRows(mod,1, &clb, &cub, cofs, cidx, cval); Clp_setRowName(mod,2*n+m,"CUT"); //Clp_writeMps(mod, "TST_DBG_1.mps", 0, 1, 1.0); // column double llb =0.0; double lub = INFINITY; double lobj =0.0; int lofs[2] = {0,21 }; int lidx[21] = { 0,1,2,3,4,5,6,7,8,9, 10,11,12,13,14,15,16,17,18,19, 20 }; double lval[21] = { -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, 1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0, 1.0 }; Clp_addColumns(mod,1, &llb, &lub, &lobj, lofs, lidx, lval); Clp_setColumnName(mod, n,"COL"); //Clp_writeMps(mod, "TST_DBG_2.mps", 0, 1, 1.0); Clp_initialSolve(mod); printf("*** model status: "); switch (Clp_status(mod)) { case 0: printf("optimal\n"); break; case 1: case 2: printf("infeasible\n"); break; default: printf("unknown\n"); break; } printf("*** objective value: %.4f\n",Clp_objectiveValue(mod)); printf("*** solution:\n"); for (int j=0; j<n+1; j++) { Clp_columnName(mod, j, buf); printf("*** %s: %.3f\n", buf,Clp_primalColumnSolution(mod)[j]); } Clp_deleteModel(mod); } — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#113?email_source=notifications&email_token=ABWJYHFGL3Y7U7CKZOU5LITQHQGQDA5CNFSM4ISXWM5KYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HIVCCHA>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABWJYHBFOUGZKQGDVYOKWO3QHQGQDANCNFSM4ISXWM5A>.

[svigerske]

Probably fixed by d167538. Reopen if not.

[uhrm]

Is there a reason why the fix for this issue (commit d167538) is not included in the latest release (1.17.4)?

[svigerske]

Probably because it extends the API and (often) we try to avoid this within the a stable branch. Would it make your life much easier if one would have this in Clp 1.17, too?

[uhrm]

I wasn't aware that the new ClpModel::synchronizeMatrix() was a public method.

Anyways, I'm affected by this bug (that's why I reported it). But it is not a show stopper.

If you won't include it in the 1.17.x release branch are there any plans for version 1.18?

[svigerske]

Ah good point, we can just add this as private method for 1.17. Then that fix will be in the next 1.17.x release.

[Mizux]

after investigation this error is throw in this call:

clp_->addRows(build_object);

ref: https://github.com/google/or-tools/blob/45770b833997f827d322e929b1ed4781c4e60d44/ortools/linear_solver/clp_interface.cc#L380

note: before this call if adding a clp_->matrix() I get a null pointer i.e.there is no packed matrix at this point...

[svigerske]

oh, what is "this error"? this issue is closed at the moment.
Did you mean to add this comment to #130?

[Mizux]

erf, sorry, yes wrong issue -> I'll copy it to the other issue feel free to erase them...