frobenius number

Nonlinear Optimization over a Weighted Independence System

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , ,

    We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

    Hard equality constrained integer knapsacks

  • Karen I. Aardal
  • Arjen K. Lenstra
    • Categories Integer Programming Tags , ,

    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 branch-and-bound, even if the number of variables is as … Read more