Piecewise linear valued constraint satisfaction problems with fixed number of variables

DOI10.1007/978-3-030-63072-0_21MaRDI QIDQ2056915zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Marcello Mamino, C. Viola

Publication date 8 December 2021

Full work available at URL https://arxiv.org/abs/2003.00963

zbMATH Keywords

fixed dimensioninfinite-domain optimisationlinear programmingpiecewise linear cost functionsvalued constraint satisfaction

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: Many combinatorial optimisation problems can be modelled as valued constraint satisfaction problems. In this paper, we present a polynomial-time algorithm solving the valued constraint satisfaction problem for a fixed number of variables and for piecewise linear cost functions. Our algorithm finds the infimum of a piecewise linear function and decides whether it is a proper minimum.

Recommendations

• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• Linear programs for constraint satisfaction problems
• scientific article; zbMATH DE number 1131737
• The Linear Complementarity Problems with a Few Variables per Constraint
• Solving Piecewise-Linear Programs: Experiments with a Simplex Approach
• Solving set-valued constraint satisfaction problems
• An algorithm for linearly-constrained piecewise lexicographic programming problems.
• On solving mixed-integer constraint satisfaction problems with unbounded variables
• A new approach to partial constraint satisfaction problems
• The complexity of valued constraint satisfaction problems

Cites work

• A new polynomial-time algorithm for linear programming
• A unifying approach to temporal constraint reasoning
• Algebraic properties of valued constraint satisfaction problem
• Constraint satisfaction problems over numeric domains
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• Integer optimization on convex semialgebraic sets
• Integer Programming with a Fixed Number of Variables
• Linear Programming in Linear Time When the Dimension Is Fixed
• Non-dichotomies in Constraint Satisfaction Complexity
• Reducibility among combinatorial problems
• The complexity of general-valued CSPs
• The interior-point revolution in optimization: History, recent developments, and lasting consequences
• The power of linear programming for general-valued CSPs
• Variational Analysis

Cited in

(1)

• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

This page was built for publication: Piecewise linear valued constraint satisfaction problems with fixed number of variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056915)