domain propagation

Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories Integer Programming Tags , , , ,

    Fast domain propagation of linear constraints has become a crucial component of today’s best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, … Read more

    Structure-driven fix-and-propagate heuristics for mixed integer programming

  • Timo Berthold
  • Gerald Gamrath
  • Stefan Heinz
  • Michael Winkler
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously … Read more