| |
Name | heart-cleveland_q |
Classification | nc|bc|d2 |
Problem type | maxfs |
Description | Bilinear model for the MaxFS instance heart-cleveland_q |
| |
Objective sense | min |
Variables | 905 (297 binary, 0 general integer, 608 continuous) |
Nonlinear variables | 608 |
Constraints | 594 |
Nonlinear constraints | 297 |
Linear nonzeros | 4017 |
Nonlinear nonzeros | 297 |
| |
Download | heart-cleveland_q.pip.gz heart-cleveland_q.gms.gz heart-cleveland_q.mod.gz |
Best known solution | |
Best known objective | |
Best known bound | |
| |
Originator | Marc Pfetsch |
Formulator | Marc Pfetsch |
Donator | Marc Pfetsch |
| |
References |
AmaldiBruglieriCasale2008
Pfetsch2008
FrankAsuncion2010
|
Links |
The Maximum Feasible Subsystem problem Home page UCI Machine Learning Repository |
| |
Additional information | This 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.
|
| |