Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|

Simon Felix | 2450 | 167 | 1.80178e-02 | hard | fhnw-sq | Infeasible | fhnw-sq3.mps.gz |

Combinatorial toy feasibility problem: Magic square. This instance is hard for all MIP solvers, but can be solved by customized codes. Infact, infeasibility can be deduced from a look at the model as explained by Ed Klotz: “But the easiest way is just by looking at the model itself. It’s a magic square problem with a few side constraints. Just remove the side constraints, and for that matter you can even remove remove the constraints on the sums of the diagonals of the square. So you are left to fill in a 7x7 magic square where the row sums are an even number (1544). If you look at the 49 values to place in the square, exactly 2 of them are odd. Regardless of where you place them, you are guaranteed to have at least 2 rows or columns involving one odd and 6 even numbers. Those rows cannot possibly add up to an even number, so no feasible solution exists.””

Detailed explanation of the following tables can be found here.

Original | Presolved | |
---|---|---|

Variables | 2450 | 2450 |

Constraints | 167 | 167 |

Binaries | 2401 | 2401 |

Integers | 49 | 49 |

Continuous | 0 | 0 |

Implicit Integers | 0 | 49 |

Fixed Variables | 0 | 0 |

Nonzero Density | 0.0180178 | 0.0180178 |

Nonzeroes | 7372 | 7372 |

Original | Presolved | |
---|---|---|

Total | 183 | 183 |

Empty | 0 | 0 |

Free | 0 | 0 |

Singleton | 0 | 0 |

Aggregations | 0 | 0 |

Precedence | 4 | 4 |

Variable Bound | 0 | 0 |

Set Partitioning | 98 | 98 |

Set Packing | 0 | 0 |

Set Covering | 0 | 0 |

Cardinality | 0 | 0 |

Invariant Knapsack | 0 | 0 |

Equation Knapsack | 0 | 0 |

Bin Packing | 0 | 0 |

Knapsack | 0 | 0 |

Integer Knapsack | 16 | 16 |

Mixed Binary | 0 | 0 |

General Linear | 65 | 65 |

Indicator | 0 | 0 |

Available nonzero structure and decomposition information. Further information can be found here.

Decomposed structure of original problem (dec-file)

Decomposed structure after trivial presolving (dec-file)

value | min | median | mean | max | |
---|---|---|---|---|---|

Components | 1.662758 | ||||

Constraint % | 0.598802 | 0.705256 | 0.598802 | 4.19162 | |

Variable % | 1.918370 | 2.088890 | 1.918370 | 7.67347 | |

Score | 0.308520 |

No solution available for fhnw-sq3 .

The following instances are most similar to fhnw-sq3 in the collection. This similarity analysis is based on 100 scaled instance features describing properties of the variables, objective function, bounds, constraints, and right hand sides.

Instance | Status | Variables | Binaries | Integers | Continuous | Constraints | Nonz. | Submitter | Group | Objective | Tags |
---|---|---|---|---|---|---|---|---|---|---|---|

fhnw-sq2 | hard | 650 | 625 | 25 | 0 | 91 | 1968 | Simon Felix | fhnw-sq | 0 | feasibility precedence set_partitioning integer_knapsack general_linear |

neos-5125849-lopori | easy | 8130 | 8040 | 90 | 0 | 453 | 20938 | Jeff Linderoth | neos-pseudoapplication-42 | 0 | feasibility benchmark_suitable aggregations set_partitioning set_packing equation_knapsack general_linear |

fiball | easy | 34219 | 33960 | 258 | 1 | 3707 | 104792 | MIPLIB submission pool | – | 138 | benchmark decomposition benchmark_suitable aggregations precedence set_partitioning general_linear |

neos-3004026-krka | easy | 17030 | 16900 | 130 | 0 | 12545 | 41860 | Jeff Linderoth | neos-pseudoapplication-38 | 0 | benchmark feasibility benchmark_suitable set_partitioning general_linear |

neos-1354092 | easy | 13702 | 13282 | 420 | 0 | 3135 | 187187 | NEOS Server Submission | neos-pseudoapplication-47 | 46 | benchmark decomposition benchmark_suitable variable_bound set_partitioning general_linear |

`No bibliographic information available`

Last Update Mar 04, 2024 by Julian Manns

generated with R Markdown

© 2023 by Zuse Institute Berlin (ZIB)

Imprint