Mikhail S. Nediak

The Maximum Box Problem and its Application to Data Analysis

  • Jonathan Eckstein
  • Peter L. Hammer
  • Ying Liu
  • Mikhail S. Nediak
  • Bruno Simeone
    • Categories Combinatorial Optimization, Data-Mining Tags , ,

    Given two finite sets of points $X^+$ and $X^-$ in $\R^n$, the maximum box problem consists in finding an interval (“box”) $B=\{x : l \leq x \leq u\}$ such that $B\cap X^-=\emptyset$, and the cardinality of $B\cap X^+$ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements … Read more

    Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming

  • Jonathan Eckstein
  • Mikhail S. Nediak
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Parallel Algorithms Tags , ,

    We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more