POLIP

library for polynomially constrained
mixed-integer programming

polip :: contents / contributors / instances / archive / bibliography

Hard  bip_cross_min.14.14.117.1

Namebip_cross_min.14.14.117.1
Classificationnc|bc|d2
Problem typequadratic_linear_ordering
Descriptionedge-crossing minimization in bipartite graphs modeled as a quadratic linear ordering problem
Objective sensemin
Variables183  (182 binary, 0 general integer, 1 continuous)
Nonlinear variables1
Constraints1456
Nonlinear constraints1
Linear nonzeros4368
Nonlinear nonzeros3892
Download bip_cross_min.14.14.117.1.pip.gz bip_cross_min.14.14.117.1.gms.gz bip_cross_min.14.14.117.1.mod.gz bip_cross_min.14.14.117.1.zpl.gz
Best known solutionbip_cross_min.14.14.117.1.sol.gz
Best known objective1973
Best known bound1973
OriginatorChristoph Buchheim, Angelika Wiegele, Lanbo Zheng
FormulatorUlrike Pagacz
DonatorChristoph Buchheim
References BuchheimWiegeleZheng2010
Links
Additional informationThis 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.

© by maintainers  |     |  imprint