Re: [Help-glpk] Transforming a Piecewise Linear Functions in a Convex Predicate

[Andrew Makhorin]

> I need to transform a Piecewise Linear Functions in a Convex
> Predicate. In attachment there is a tex file with the function and my  
> transformation in a convex predicate. Using that convex predicate in a  
> milp, the milp does not found solution. So in attachment there is  
> my .c file with the function that create the MILP and an output with a  
> milp with random valute.
> The function in the examples is repeated two times, but it does not  
> matter.

> I don't know where is my mistake. It's impossible for me find it.

Below here is the output from glpsol (mip preprocessing is disabled,
debug output is enabled), which shows in details why your mip instance
has no integer feasible solution:

GLPSOL: GLPK LP/MIP Solver 4.39
Reading problem data from `milp.txt'...
27 rows, 10 columns, 69 non-zeros
10 integer variables, 9 of which are binary
59 lines were read
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.288e+02  ratio =  1.288e+02
GM: min|aij| =  5.546e-01  max|aij| =  1.803e+00  ratio =  3.252e+00
EQ: min|aij| =  3.161e-01  max|aij| =  1.000e+00  ratio =  3.163e+00
Crashing...
Size of triangular part = 27
glp_simplex: original LP has 27 rows, 10 columns, 69 non-zeros
glp_simplex: presolved LP has 21 rows, 10 columns, 52 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.288e+02  ratio =  1.288e+02
GM: min|aij| =  6.238e-01  max|aij| =  1.603e+00  ratio =  2.570e+00
EQ: min|aij| =  3.977e-01  max|aij| =  1.000e+00  ratio =  2.514e+00
Crashing...
Size of triangular part = 21
      0: obj =   0.000000000e+00  infeas =  4.684e+00 (0)
*    10: obj =   1.000000000e+00  infeas =  4.926e-16 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
------------------------------------------------------------------------
Processing node 1 at level 0
+    10: mip =     not found yet <=              +inf        (1; 0)
Solving LP relaxation...
|    10: obj =   1.000000000e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Found optimal solution to LP relaxation
Local bound is 1.000000000e+00
There are 6 fractional columns, integer infeasibility is 1.203e+00
branch_drtom: column 7 chosen to branch on
branch_drtom: down-branch bound is 1.000000000e+00
branch_drtom: up-branch   is infeasible
Up-branch is hopeless
+    10: mip =     not found yet <=   1.000000000e+00        (1; 0)
Solving LP relaxation...
|    11: obj =   1.000000000e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Found optimal solution to LP relaxation
Local bound is 1.000000000e+00
There are 3 fractional columns, integer infeasibility is 1.113e+00
branch_drtom: column 4 chosen to branch on
branch_drtom: down-branch bound is 1.000000000e+00
branch_drtom: up-branch   bound is 1.000000000e+00
Branching on column 4, primal value is 6.291208791e-01
Node 2 begins down branch, node 3 begins up branch 
------------------------------------------------------------------------
Processing node 3 at level 1
+    11: mip =     not found yet <=   1.000000000e+00        (2; 0)
Solving LP relaxation...
|    12: obj =   1.000000000e+00  infeas =  0.000e+00 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
LP relaxation has no feasible solution
Node 3 fathomed
------------------------------------------------------------------------
Processing node 2 at level 1
+    12: mip =     not found yet <=   1.000000000e+00        (1; 1)
Solving LP relaxation...
|    15: obj =   1.000000000e+00  infeas =  0.000e+00 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
LP relaxation has no feasible solution
Node 2 fathomed
Active list is empty!
+    15: mip =     not found yet <=     tree is empty        (0; 3)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.1 Mb (57684 bytes)


I would suggest you to use the MathProg modeling language. It is
much easier than writing a model generator in C.

See also:
http://lists.gnu.org/archive/html/help-glpk/2008-12/msg00126.html
http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html


Andrew Makhorin