Gabor Pataki The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program (P) \sup { | Ax \leq_K b} in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana’s dual … Read more
A closed convex cone K is called nice, if the set K^* + F^\perp is closed for all F faces of K, where K^* is the dual cone of K, and F^\perp is the orthogonal complement of the linear span of F. The niceness property plays a role in the facial reduction algorithm of Borwein … Read more
We call a conic linear system (P) Ax \leq_K b {\em well behaved}, if for all $c$ objective functions the value of \sup \, \{ \, \la c, x \ra \, | \, Ax \leq_K b \, \} and of its dual agree, and the latter is attained, when finite. We call $(P)$ {\em badly … Read more
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (i.e. the dense part of the … Read more
We prove that the subset sum problem has a polynomial time computable certificate of infeasibility for all $a$ weight vectors with density at most $1/(2n)$ and for almost all integer right hand sides. The certificate is branching on a hyperplane, i.e. by a methodology dual to the one explored by Lagarias and Odlyzko; Frieze; Furst … Read more
We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more
We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\’asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and … Read more
We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’ ≤ Ax ≤ b, x ∈ Zn with b’ ≤ (AU)y ≤ b, y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more
When is the linear image of a closed convex cone closed? We present very simple, and intuitive necessary conditions, which 1) unify, and generalize seemingly disparate, classical sufficient conditions: polyhedrality of the cone, and “Slater” type conditions; 2) are necessary and sufficient, when the dual cone belongs to a class, that we call nice cones. … Read more