 
Name  tictactoe_q 
Classification  ncbcd2 
Problem type  maxfs 
Description  Bilinear model for the MaxFS instance tictactoe_q 
 
Objective sense  min 
Variables  2884 (958 binary, 0 general integer, 1926 continuous) 
Nonlinear variables  1926 
Constraints  1916 
Nonlinear constraints  958 
Linear nonzeros  10139 
Nonlinear nonzeros  958 
 
Download  tictactoe_q.pip.gz tictactoe_q.gms.gz tictactoe_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 branchandcut 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.

 