  


Hard equality constrained integer knapsacks
Karen Aardal (aardalisye.gatech.edu) Abstract: We consider the following integer feasibility problem: ``Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = a_0$?'' Some instances of this type have been found to be extremely hard to solve by standard methods such as branchandbound, even if the number of variables is as small as ten. We observe that not only the sizes of the numbers $a_0,\ a_1,\dots,a_n,$ but also their structure, have a large impact on the difficulty of the instances. This particular structure enables us to derive a strong lower bound on the Frobenius number for these instances. Moreover, we demonstrate that the same structural characteristics that make the instances so difficult to solve by branchandbound make the solution of a certain reformulation of the problem almost trivial. We accompany our results by a small computational study. Keywords: Lattice basis reduction, branching on hyperplanes, Frobenius number Category 1: Integer Programming Citation: Preprint number 1256, Department of Mathematics, Utrecht University, Utrecht, The Netherlands, 2002. Download: [Postscript] Entry Submitted: 11/03/2002 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  