Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
作者：
Highlights：
• Constraint satisfaction with semilinear relations and addition is in P or is NP-hard.
• We present an algorithm for a subfamily of problems based on computing affine hulls.
• Linear optimisation is often polynomial-time equivalent to the decision problem.
• We characterise those problems where integer feasibility equals rational feasibility.
摘要
•Constraint satisfaction with semilinear relations and addition is in P or is NP-hard.•We present an algorithm for a subfamily of problems based on computing affine hulls.•Linear optimisation is often polynomial-time equivalent to the decision problem.•We characterise those problems where integer feasibility equals rational feasibility.
论文关键词：Constraint satisfaction problems,Semilinear sets,Algorithms,Computational complexity
论文评审过程：Received 18 May 2015, Revised 22 February 2016, Accepted 7 March 2016, Available online 17 March 2016, Version of Record 1 April 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.03.002
