search

mr-ma / composition-framework

1 stars 3 forks source link

ILP fails to find a solution for the toast program #24

Open mr-ma opened 5 years ago

mr-ma commented 5 years ago

Tried maximising manifest for the toast program:

Error: basis matrix is singular to working precision (cond = 5.24e+15)
GLPK Integer Optimizer, v4.65
118531 rows, 84715 columns, 367791 non-zeros
84715 integer variables, all of which are binary
glp_intopt: optimal basis to initial LP relaxation not provided
Writing basic solution to '/home/sip/eval/binaries/toast.x.bc/100/0/1/solution.txt'...
203255 lines were written
Writing MIP solution to '/home/sip/eval/binaries/toast.x.bc/100/0/1/solution_readable.txt'...
ILP resuls. max manifest.  overhead: 0.000000e+00 explicit instruction coverage: 0 implicit instruction coverage: 0
Adding 0 manifests to protection graph
#0/0
dennisfischer commented 5 years ago

Hi,

This is a wanted behavior. It does not loop infinitely. After ILP runs we check with the protection graph for cycles. If cycles still exist we rerun the ILP with an added constraint.

The alternative was to enumerate all cycles. However, attempts of writing such an analysis we're not promising (too many combinations)

Am 09.05.2019 11:17 schrieb mr-ma notifications@github.com:

Tried maximising manifest for the toast program:

Error: basis matrix is singular to working precision (cond = 5.24e+15) GLPK Integer Optimizer, v4.65 118531 rows, 84715 columns, 367791 non-zeros 84715 integer variables, all of which are binary glp_intopt: optimal basis to initial LP relaxation not provided Writing basic solution to '/home/sip/eval/binaries/toast.x.bc/100/0/1/solution.txt'... 203255 lines were written Writing MIP solution to '/home/sip/eval/binaries/toast.x.bc/100/0/1/solution_readable.txt'... ILP resuls. max manifest. overhead: 0.000000e+00 explicit instruction coverage: 0 implicit instruction coverage: 0 Adding 0 manifests to protection graph

0/0

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/dennisfischer/composition-framework/issues/24, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AALKMJK5KPVRJYKRDTHBNRLPUPT3RANCNFSM4HLYVF4Q.

mr-ma commented 5 years ago

@dennisfischer I think you're talking about #23 not #24, right?

dennisfischer commented 5 years ago

Yes

Am 09.05.2019 13:01 schrieb mr-ma notifications@github.com:

@dennisfischerhttps://github.com/dennisfischer I think you're talking about #23https://github.com/dennisfischer/composition-framework/issues/23 not #24https://github.com/dennisfischer/composition-framework/issues/24, right?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/dennisfischer/composition-framework/issues/24#issuecomment-490857815, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AALKMJODTJM6K74OW33RBXTPUQAALANCNFSM4HLYVF4Q.

mr-ma commented 5 years ago

same goes for dkstra-large and say !

dennisfischer commented 5 years ago

Will have a look at it.

Am 09.05.2019 17:21 schrieb mr-ma notifications@github.com:

same goes for dkstra-large and say !

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/dennisfischer/composition-framework/issues/24#issuecomment-490949347, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AALKMJLPFRFUY6DMC7G5NY3PUQ6RPANCNFSM4HLYVF4Q.

dennisfischer commented 5 years ago

Problem: matrix is singular => not invertible which glpk probably uses.

Proposed solution: run glp_std_basis(lp) or glp_adv_basis(lp, 0) before calls to glp_simplex. The resulting matrix should not be singular and ILP can proceed. Chosing a different basis may increase runtime overhead.

I'll try these today evening if you have not tried them in the meantime.

Am 09.05.2019 18:00 schrieb Dennis Fischer dennis.fischer@live.com: Will have a look at it.

Am 09.05.2019 17:21 schrieb mr-ma notifications@github.com:

same goes for dkstra-large and say !

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/dennisfischer/composition-framework/issues/24#issuecomment-490949347, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AALKMJLPFRFUY6DMC7G5NY3PUQ6RPANCNFSM4HLYVF4Q.

dennisfischer commented 5 years ago

glp_std_basis and glp_adv_basis were not necessary for me any longer. I've changed the way the integer optimization is called. We were apparently doing it slightly wrong. We ran glp_simplex then glp_intopt. glp_simplex failed for some cases with singular matrix. Instead, we should've used the presolve flag such that we can run glp_intopt without glp_simplex. If the matrix is singular now, glp_intopt will retry with a different basis.

dennisfischer commented 5 years ago

Review that this is fixed

mr-ma commented 5 years ago

@dennisfischer should I check this with the better-ilp branch?

dennisfischer commented 5 years ago

@mr-ma Yes, should work on both branches better-ilp and precise-explicit