[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Redundant condition detection

From: Neill Clift
Subject: Redundant condition detection
Date: Wed, 13 Oct 2021 00:12:59 +0000


I am currently using winglpk to detect if a small integer inequality system is feasible. No objective function just feasibility.

If the system is found to be feasible then I call glpk for each condition in the system with that condition removed and instead specified as the objective function.


So for example if one of my conditions is a – b + c >= 3 then I remove that condition and have an objective function of a – b + c and find its minimum.

If it’s minimum is >= 3  I conclude the condition is redundant and remove it (it wasn’t limiting the problem).

If redundant the condition is removed and the attempts at reduction continue.


I do this in a program with a very large number of systems. I currently rebuild the problem from scratch for each condition (glp_erase_prob first).

I want to improve the performance of this. I would like to have some input on what might be the best way to do this.

I can see I could delete rows, update the objective and optimize again. I would have to tracks the rows used.

Is there a way to use something like glp_analyze_bound to obtain information I could use for this?


I am calling glpk from 256 threads concurrently. This seems to work just fine but the documentation suggests it’s not thread safe. I am assuming this is for sharing a lp program between threads rather than having a problem per thread? I only change things relating to a problem (glp_prob* type calls).




reply via email to

[Prev in Thread] Current Thread [Next in Thread]