Hi,
I am interested in techniques that can prove that an integer linear program has no solutions. I am just looking at feasibility and have no objective function to maximize etc.
This is part of the best known algorithm for calculation optimal addition chains. The system I want to check for infeasibility is quite simple. It's just the Frobenius diophantine equation with an upper bound on the variables.
$\sum_{i=1}^{z}a_{i}x_{i}=n$
With $1\leq x_{i}\leq u$. $a_i$ and $n$ are constants determined by a partial search for an addition chains.
The code that uses this will try to solve billions of small problems like this.
I currently use branch and bound to try and prove there are no solutions or reject the few there are with additional problem constraints.
You can bring back to an optimization problem by optimizing any linear function over the integer feasible solutions set, for example the sum of all the variables, and use Cplex.
Thanks for the responses. I can't use something like cplex since this is part of another program generating billions of these problems. I need fast techniques to try and eliminate cases.
Checking feasibility of an equality-constrained knapsack problem is a classic NP-complete problem, which has applications in cryptography.
If the right-hand side is reasonably small, you can solve the problem with dynamic programming.
If that is not the case, you could try the lattice basis reduction methods developed by Karen Aardal and others.
You could use FeasOpt optimizer in CPLEX to find out infeasility.
https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/infeas_unbd/feasopt/02_feasopt_defn.html
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Control Theory
- Control Systems