POLIP

library for polynomially constrained
mixed-integer programming


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

Open  prob.5.090.100.0_q

Nameprob.5.090.100.0_q
Classificationnc|bc|d2
Problem typemaxfs
DescriptionBilinear model for the MaxFS instance prob.5.090.100.0_q
Objective sensemin
Variables275  (90 binary, 0 general integer, 185 continuous)
Nonlinear variables185
Constraints180
Nonlinear constraints90
Linear nonzeros714
Nonlinear nonzeros90
Download prob.5.090.100.0_q.pip.gz prob.5.090.100.0_q.gms.gz prob.5.090.100.0_q.mod.gz
Best known solution
Best known objective
Best known bound
OriginatorMarc Pfetsch
FormulatorMarc Pfetsch
DonatorMarc Pfetsch
References AmaldiBruglieriCasale2008 Pfetsch2008 FrankAsuncion2010
Links The Maximum Feasible Subsystem problem Home page UCI Machine Learning Repository
Additional informationThis is a bilinear (quadratic, complementary) model for the complementary problem of the maximum feasible subsystem problem (MaxFS). Given an infeasible linear inequality system, the MaxFS problem consists of finding a subsystem of largest cardinality that is feasible. The complementary problem removes the least number of inequalities such that the resulting system is feasible. The model introduces a slack variable for each linear inequality and a binary variable that indicates whether a certain inequality is fulfilled or not. For each inequality the corresponding two variables are coupled via a complementary constraint, i.e., at least one of them must be 0. This is a classical formulation. It has been used, for instance, in Amaldi et al. [2008]. A description of a branch-and-cut algorithm and more information about the problem can be found in Pfetsch [2008]. The original instances can be accessed through the Maximum Feasible Subsystem problem Home page. Some instances are based on data from the UCI Machine Learning Repository.

© by maintainers  |     |  imprint