Small program that seems to loop
Neill Clift <[email protected]> Fri, 16 Oct 2020 02:39:02 +0000
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <MWHPR15MB17128E1BEDF78268D4D9A97CB5030@MWHPR15MB1712.namprd15.prod.outlook.com> |
Hi,
I am running on Windows 10 with VS 2019 16.7.5.
I just cut and pasted some old code I had that found minimum values for entries in an addition chain for a small project were I just wanted to know if a system was feasible over the integers.
I may have done something wrong (for example I still have a call to set the objective function as a MIN but there is no objective function).
I generate the small systems programmatically. Seems to work find for a lot of the generated systems but I found one that doesn't seem to return from the integer portion.
At the top of the code is a symbolic representation of the problem in a comment.
I attach this program just in case this is interesting to find a bug etc.
Thanks.
Neill.
GLPK Simplex Optimizer, v4.65
30 rows, 17 columns, 62 non-zeros
0: obj = 0.000000000e+00 inf = 2.800e+01 (28)
18: obj = 0.000000000e+00 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.65
30 rows, 17 columns, 62 non-zeros
17 integer variables, none of which are binary
Preprocessing...
28 rows, 17 columns, 60 non-zeros
17 integer variables, none of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 2.000e+00 ratio = 2.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 28
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
28 rows, 17 columns, 60 non-zeros
18: obj = 0.000000000e+00 inf = 1.000e+00 (1)
23: obj = 0.000000000e+00 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 23: mip = not found yet >= -inf (1; 0)
+ 11325: mip = not found yet >= 0.000000000e+00 (8782; 0)
+ 17611: mip = not found yet >= 0.000000000e+00 (13272; 0)
+ 22532: mip = not found yet >= 0.000000000e+00 (16787; 0)
+ 26757: mip = not found yet >= 0.000000000e+00 (19805; 0)
+ 30527: mip = not found yet >= 0.000000000e+00 (22498; 0)
+ 33970: mip = not found yet >= 0.000000000e+00 (24957; 0)
+ 37157: mip = not found yet >= 0.000000000e+00 (27234; 0)
+ 40148: mip = not found yet >= 0.000000000e+00 (29370; 0)
+ 42955: mip = not found yet >= 0.000000000e+00 (31375; 0)
+ 45622: mip = not found yet >= 0.000000000e+00 (33280; 0)
Time used: 60.0 secs. Memory used: 15.0 Mb.
+ 48170: mip = not found yet >= 0.000000000e+00 (35100; 0)
+ 50604: mip = not found yet >= 0.000000000e+00 (36839; 0)
+ 52948: mip = not found yet >= 0.000000000e+00 (38513; 0)
+ 55208: mip = not found yet >= 0.000000000e+00 (40127; 0)
+ 57387: mip = not found yet >= 0.000000000e+00 (41684; 0)
+ 59501: mip = not found yet >= 0.000000000e+00 (43194; 0)
+ 61558: mip = not found yet >= 0.000000000e+00 (44663; 0)
+ 63552: mip = not found yet >= 0.000000000e+00 (46087; 0)
+ 65490: mip = not found yet >= 0.000000000e+00 (47471; 0)
+ 67381: mip = not found yet >= 0.000000000e+00 (48822; 0)
+ 69228: mip = not found yet >= 0.000000000e+00 (50141; 0)
+ 71023: mip = not found yet >= 0.000000000e+00 (51424; 0)
Time used: 120.0 secs. Memory used: 22.9 Mb.
+ 72782: mip = not found yet >= 0.000000000e+00 (52680; 0)
+ 74492: mip = not found yet >= 0.000000000e+00 (53901; 0)
+ 76167: mip = not found yet >= 0.000000000e+00 (55098; 0)
+ 77818: mip = not found yet >= 0.000000000e+00 (56277; 0)
+ 79427: mip = not found yet >= 0.000000000e+00 (57426; 0)
+ 80997: mip = not found yet >= 0.000000000e+00 (58548; 0)
+ 82477: mip = not found yet >= 0.000000000e+00 (59605; 0)
+ 83985: mip = not found yet >= 0.000000000e+00 (60682; 0)
+ 85422: mip = not found yet >= 0.000000000e+00 (61709; 0)
+ 86862: mip = not found yet >= 0.000000000e+00 (62737; 0)
+ 88340: mip = not found yet >= 0.000000000e+00 (63793; 0)
...
test.cpp
(text/plain, 4.5 KB)
// test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "glpk.h"
int __cdecl main(int argc,char *argv[])
{
// a = b + b > b = c + c > c = d + d > d = e + e > e = f + f > f = g + g > g = h + h > h = i + j > i = k + q > j = m + n > k = l + p > l = o + o > m > n > o > p > q > 0
int ia[] = { 0,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,16,17,17,18,18,18,19,19,20,20,20,21,21,22,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30 };
int ja[] = { 0,1,1,2,1,2,2,3,2,3,3,4,3,4,4,5,4,5,5,6,5,6,6,7,6,7,7,8,7,8,8,9,10,8,9,9,11,17,9,10,10,13,14,10,11,11,12,16,11,12,12,15,12,13,13,14,14,15,15,16,16,17,17 };
double ar[] = { 0.0,1.0,1.0,-2.0,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-2.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,1.0,-1.0,1.0,-2.0,1.0,-1.0,1.0,-1.0,1.0,-1.0,1.0,-1.0,1.0,-1.0,1.000000 };
glp_prob* lp = glp_create_prob();
glp_set_prob_name(lp, "Addition Chain");
glp_set_obj_dir(lp, GLP_MIN);
glp_add_rows(lp, 30);
glp_add_cols(lp, 17);
glp_set_row_bnds(lp, 1, GLP_FR, 0.0, 0.000000);
glp_set_row_bnds(lp, 2, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 3, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 4, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 5, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 6, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 7, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 8, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 9, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 10, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 11, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 12, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 13, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 14, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 15, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 16, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 17, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 18, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 19, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 20, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 21, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 22, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 23, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 24, GLP_FX, 0.0, 0.0);
glp_set_row_bnds(lp, 25, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 26, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 27, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 28, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 29, GLP_LO, 1.0, 0.0);
glp_set_row_bnds(lp, 30, GLP_LO, 1.0, 0.0);
glp_set_col_bnds(lp, 1, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 1, GLP_IV);
glp_set_col_bnds(lp, 2, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 2, GLP_IV);
glp_set_col_bnds(lp, 3, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 3, GLP_IV);
glp_set_col_bnds(lp, 4, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 4, GLP_IV);
glp_set_col_bnds(lp, 5, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 5, GLP_IV);
glp_set_col_bnds(lp, 6, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 6, GLP_IV);
glp_set_col_bnds(lp, 7, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 7, GLP_IV);
glp_set_col_bnds(lp, 8, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 8, GLP_IV);
glp_set_col_bnds(lp, 9, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 9, GLP_IV);
glp_set_col_bnds(lp, 10, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 10, GLP_IV);
glp_set_col_bnds(lp, 11, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 11, GLP_IV);
glp_set_col_bnds(lp, 12, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 12, GLP_IV);
glp_set_col_bnds(lp, 13, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 13, GLP_IV);
glp_set_col_bnds(lp, 14, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 14, GLP_IV);
glp_set_col_bnds(lp, 15, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 15, GLP_IV);
glp_set_col_bnds(lp, 16, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 16, GLP_IV);
glp_set_col_bnds(lp, 17, GLP_LO, 1.0, 0.0);
glp_set_col_kind(lp, 17, GLP_IV);
//glp_term_out(GLP_OFF);
glp_load_matrix(lp, 62, ia, ja, ar);
glp_simplex(lp, NULL);
if (glp_get_status(lp) != GLP_OPT) {
if (glp_get_status(lp) != GLP_NOFEAS) {
printf("%d\n", glp_get_status(lp));
}
} else {
glp_iocp param;
glp_init_iocp(¶m);
param.presolve = GLP_ON;
int intopt = glp_intopt(lp, ¶m);
if (intopt == 0) {
int mipstatus = glp_mip_status(lp);
if (mipstatus == GLP_NOFEAS) {
} else if (mipstatus != GLP_FEAS && mipstatus != GLP_OPT) {
printf("glp_mip_status failed %d\n", mipstatus);
exit(0);
}
} else {
printf("glp_intopt failed %d\n", intopt);
exit(0);
}
}
glp_delete_prob(lp);
}