 
Name  bip_cross_min.20.20.40.1 
Classification  ncbcd2 
Problem type  quadratic_linear_ordering 
Description  edgecrossing minimization in bipartite graphs modeled as a quadratic linear ordering problem 
 
Objective sense  min 
Variables  381 (380 binary, 0 general integer, 1 continuous) 
Nonlinear variables  1 
Constraints  4560 
Nonlinear constraints  1 
Linear nonzeros  13680 
Nonlinear nonzeros  965 
 
Download  bip_cross_min.20.20.40.1.pip.gz bip_cross_min.20.20.40.1.gms.gz bip_cross_min.20.20.40.1.mod.gz bip_cross_min.20.20.40.1.zpl.gz 
Best known solution  bip_cross_min.20.20.40.1.sol.gz 
Best known objective  57 
Best known bound  57 
 
Originator  Christoph Buchheim, Angelika Wiegele, Lanbo Zheng 
Formulator  Ulrike Pagacz 
Donator  Christoph Buchheim 
 
References 
BuchheimWiegeleZheng2010

Links 

 
Additional information  This instance is for the edge crossing minimization problem in a
bipartite graph G. G has to be drawn in the plane so that the nodes of
its two shores are placed on two parallel horizontal lines. The task
is to minimize the number of edge crossings by permuting the order of
nodes on each layer, assuming that all edges are drawn as straight
lines. The problem can be modeled as a quadratic objective over linear
ordering variables. The instance is from BuchheimWiegeleZheng2010.

 