TY - GEN
T1 - Duplex Encoding of Antibandwidth Feasibility Formulas Submitted to the SAT Competition 2020
AU - Fazekas, Katalin
AU - Sinnl, Markus
AU - Biere, Armin
AU - Parragh, Sophie
PY - 2020
Y1 - 2020
N2 - This benchmark set is originating in our recent work on the antibandwidth problem (in short ABP) presented in [1]. The ABP is a max-min optimization problem where, for a given graph G= (V,E), the goal is to assign a unique label from the range [1,...,|V|] to each vertex v∈V, such that the smallest difference between labels of neighbouring nodes is maximal.Applications of the ABP include for example scheduling,obnoxious facility location, radio frequency assignment. To solve the ABP, in [2] an iterative solution method was proposed, where each iteration asked whether there exists a labelling to the graph, s.t. the smallest difference between labels of neighbours is greater thank. Finding the highest k where the answer is still affirmative determines the optimal solution of the ABP. In [1] we slightly refined the proposed formalization of [2] s.t. the question of each iteration can bestated as combinations of at-most-one constraints sliding overk-long sequences of binary variables.
AB - This benchmark set is originating in our recent work on the antibandwidth problem (in short ABP) presented in [1]. The ABP is a max-min optimization problem where, for a given graph G= (V,E), the goal is to assign a unique label from the range [1,...,|V|] to each vertex v∈V, such that the smallest difference between labels of neighbouring nodes is maximal.Applications of the ABP include for example scheduling,obnoxious facility location, radio frequency assignment. To solve the ABP, in [2] an iterative solution method was proposed, where each iteration asked whether there exists a labelling to the graph, s.t. the smallest difference between labels of neighbours is greater thank. Finding the highest k where the answer is still affirmative determines the optimal solution of the ABP. In [1] we slightly refined the proposed formalization of [2] s.t. the question of each iteration can bestated as combinations of at-most-one constraints sliding overk-long sequences of binary variables.
M3 - Conference proceedings
VL - B-2020-1
T3 - Department of Computer Science Report Series B
SP - 81
EP - 82
BT - Proc. of SAT Competition 2020 - Solver and Benchmark Descriptions
A2 - Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti Järvisalo, Martin Suda, null
PB - University of Helsinki
ER -