I wrote a problem using MathProg language to check whether my understanding of some mixed-integer problem was correct. After a while I was able to figure it out, and I can assume that this solution is correct.
GLPK Simplex Optimizer, v4.45
37 rows, 30 columns, 97 non-zeros
0: obj = -1.300000000e+01 infeas = 1.300e+01 (0)
* 10: obj = 7.677248677e+00 infeas = 0.000e+00 (0)
* 14: obj = 5.925925926e-01 infeas = 7.889e-31 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 14: mip = not found yet >= -inf (1; 0)
+ 15: >>>>> 5.925925926e-01 >= 5.925925926e-01 0.0% (2; 0)
+ 15: mip = 5.925925926e-01 >= tree is empty 0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2 Mb (204010 bytes)
...
Model has been successfully processed
But what I actually need is the very same routine implemented in a C++ code. It took me a while to rewrite the problem in terms of GLPK C API, but during unit testing I found out that that C++ version doesn't return a solution, as there is no feasable one.
GLPK Simplex Optimizer, v4.45
37 rows, 30 columns, 10 non-zeros
0: obj = 0.000000000e+00 infeas = 2.000e+00 (16)
PROBLEM HAS NO FEASIBLE SOLUTION
Obviously I made some mistakes and I need to find where.
Is there some debug or preview method that I can use to, for instance, see model generated by my C++ code and by MathProg model to compare them? Simply going through all the places where I could mess something up would be some solution but quite ineffective one.
After a while I figure out a way to fix my program step by step.
First run a MathProg program like this:
glpsol -m model.mod -d data.dat --output solution.txt --wglp glp.mod
Then run the broken C++ routine, and after gtl_simplex
run following commands:
glp_print_mip(problem, "broken_solution.txt");
glp_write_prob(problem, 0, "broken_glp.mod");
From solution.txt
and broken_solution.txt
I could figure out the difference between column and row constraints definition. It helps when we create mock first row equal to cost function, with free variable as a constrain. By rotating rows and column definitions we can make sure that both files will have thier respecitve rows and columns definitions in the same order.
Once those constraints are fixed we can start fixing actual data. glp.mod
and broken_glp.mod
will both contains definitions for each constraint as well as values for each row and column. They are 1-indexed, with 0-row being cost function factors.
If in C++ program we already have rows and column in the same order as in MathProg generated model we can easily compare both files - but first sort them e.g. like sort glp.mod > glp.sorted
- values for each row/column might occur in a different order even when we defined rows and columns in the same order as in MathProg file.
After a while I was able to fix my program to perform the same routine as MathProg one. The only difference was displayed accuracy, but that is only a matter of output formatting.