[Bug-glpk] cycling in the simplex method

[Ali Baharev]

Dear Andrew,

I made a hexadecimal dump of the floating point numbers in my LP
problem. With the attached files, I can reproduce cycling on different
machines and operating systems using different compilers. Just make
sure your compiler supports the %la conversion properly (C99,
hexadecimal input of floating point double).

The LP problem is extremely badly scaled. For me, it would be
perfectly acceptable if the solver reported numerical problems and
gave up the solution procedure.

Many thanks,

Ali

dump
Description: Binary data

#include "glpk.h"

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <string>

using namespace std;

int main() {

	ifstream in("dump");

	string s;

	int to_read;

	in >> to_read;

	const int k = to_read;

	int* const ia = new int[1+k];

	int* const ja = new int[1+k];

	double* const ar = new double[1+k];

	for (int i=1; i<k; ++i) {

		in >> ia[i];

		in >> ja[i];

		in >> s;

		sscanf(s.c_str(), "%la", ar+i);
	}

	in >> to_read;

	const int n = to_read;

	glp_prob* lp = glp_create_prob();

	glp_add_rows(lp, n);

	glp_add_cols(lp, n);

	for (int i=1; i<=n; ++i) {

		double lb, ub;

		in >> s;

		sscanf(s.c_str(), "%la", &lb);

		in >> s;

		sscanf(s.c_str(), "%la", &ub);

		int row_type = GLP_FX;

		if (lb != ub)
			row_type = GLP_DB;

		glp_set_row_bnds(lp, i, row_type, lb, ub);
	}

	for (int j=1; j<=n; ++j) {

		glp_set_col_bnds(lp, j, GLP_DB, -1.0, 1.0);

		glp_set_obj_coef(lp, j, 0.0);
	}

	glp_load_matrix(lp, k-1, ia, ja, ar);

	glp_write_lp(lp, 0, "dump.lp");

	glp_smcp parm;

	glp_init_smcp(&parm);

	glp_scale_prob(lp, GLP_SF_AUTO);

	glp_simplex(lp, &parm);

	glp_set_obj_coef(lp, 6, 1.0);

	glp_simplex(lp, &parm);

	glp_set_obj_coef(lp, 6, 0.0);
	glp_set_obj_coef(lp, 8, 1.0);

	glp_simplex(lp, &parm);

	glp_set_obj_coef(lp, 8,  0.0);
	glp_set_obj_coef(lp, 6, -1.0);

	glp_simplex(lp, &parm);

	glp_set_obj_coef(lp, 6, 0.0);
	glp_set_obj_coef(lp, 2, 1.0);

	glp_simplex(lp, &parm);

	glp_set_obj_coef(lp, 2, 0.0);
	glp_set_obj_coef(lp, 1, 1.0);

	glp_simplex(lp, &parm);

	printf("Never gets here!\n");

	return 0;
}


_______________________________________________
Bug-glpk mailing list
Bug-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-glpk