Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|
Michael Bastubbe | 16263 | 55107 | 2.14233e-04 | hard | graphs | -6 | graph20-80-1rand.mps.gz |
Packing Cuts in Undirected Graphs. Instances are described in 4.1.
Detailed explanation of the following tables can be found here.
Original | Presolved | |
---|---|---|
Variables | 16263 | 16146 |
Constraints | 55107 | 51714 |
Binaries | 16263 | 16146 |
Integers | 0 | 0 |
Continuous | 0 | 0 |
Implicit Integers | 0 | 0 |
Fixed Variables | 0 | 0 |
Nonzero Density | 0.000214233 | 0.000214110 |
Nonzeroes | 191997 | 178776 |
Original | Presolved | |
---|---|---|
Total | 55107 | 51714 |
Empty | 0 | 0 |
Free | 0 | 0 |
Singleton | 117 | 0 |
Aggregations | 0 | 0 |
Precedence | 0 | 3276 |
Variable Bound | 0 | 0 |
Set Partitioning | 117 | 117 |
Set Packing | 0 | 0 |
Set Covering | 27378 | 0 |
Cardinality | 0 | 0 |
Invariant Knapsack | 27495 | 48321 |
Equation Knapsack | 0 | 0 |
Bin Packing | 0 | 0 |
Knapsack | 0 | 0 |
Integer Knapsack | 0 | 0 |
Mixed Binary | 0 | 0 |
General Linear | 0 | 0 |
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 | 2.071882 | ||||
Constraint % | 0.852767 | 0.852767 | 0.852767 | 0.852767 | |
Variable % | 0.848507 | 0.848507 | 0.848507 | 0.848507 | |
Score | 0.989272 |
Find solutions below. Download the archive containing all solutions from the Download page.
## Warning in lapply(df["exactobjval"], as.numeric): NAs introduced by coercion
ID | Objective | Exact | Int. Viol | Cons. Viol | Obj. Viol | Submitter | Date | Description |
---|---|---|---|---|---|---|---|---|
2 | -6 | 0 | 0 | 0 | Hans Mittelmann | 2019-11-15 | Computed with Gurobi 8.1.1 in 8289s using 40 threads | |
1 | -6 | -6 | 0 | 0 | 0 | - | 2018-10-12 | Solution found during MIPLIB2017 problem selection. |
The following instances are most similar to graph20-80-1rand 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 |
---|---|---|---|---|---|---|---|---|---|---|---|
graph40-20-1rand | open | 31243 | 31243 | 0 | 0 | 99067 | 345557 | Michael Bastubbe | graphs | -15* | binary decomposition precedence set_partitioning invariant_knapsack |
graph20-20-1rand | easy | 2183 | 2183 | 0 | 0 | 5587 | 19277 | Michael Bastubbe | graphs | -9 | benchmark binary decomposition benchmark_suitable precedence set_partitioning invariant_knapsack |
graph40-40-1rand | open | 102600 | 102600 | 0 | 0 | 360900 | 1260900 | Michael Bastubbe | graphs | -9* | binary precedence set_partitioning invariant_knapsack |
graph40-80-1rand | open | 283648 | 283648 | 0 | 0 | 1050112 | 3671552 | Michael Bastubbe | graphs | -7* | binary precedence set_partitioning invariant_knapsack |
neos-3555904-turama | easy | 37461 | 37461 | 0 | 0 | 146493 | 793605 | Hans Mittelmann | neos-pseudoapplication-81 | -34.7 | benchmark binary benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack |
@article{or:BergnerLuebbeckeWitt:16,
Author = {
M. Bergner and M.E. L\"{u}bbecke and J.T. Witt},
Title = {A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs},
Journal = {Journal of Experimental Algorithmics (JEA)},
Year = {2016},
Volume = {21 },
Number = {2016--},
Pages = {Article No. 1.2},
Month = {Jan},
Publisher = {ACM New York, NY, USA},
DOI = {10.1145/2851492}
}