s1234

binary precedence set_covering invariant_knapsack binpacking knapsack

Submitter Variables Constraints Density Status Group Objective MPS File
Siwei Sun 2945 8418 1.80069e-03 hard SiweiSun 29 s1234.mps.gz

These models come from my cryptographic research and are used to search for the best differential characteristics of the round-reduced versions of the block cipher Serpent with the mixed-integer programming technique. For all the models, including S1234.lp, S56701.lp, S456701.lp, I have found a feasible solution in the corresponding mst file. The challenge is that can we find better solutions or can we find the best solutions.

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
Original Presolved
Variables 2945 2944
Constraints 8418 8337
Binaries 2945 2944
Integers 0 0
Continuous 0 0
Implicit Integers 0 0
Fixed Variables 0 0
Nonzero Density 0.00180069 0.00180899
Nonzeroes 44641 44400
Constraint Classification Properties
Original Presolved
Total 8418 8337
Empty 0 0
Free 0 0
Singleton 1 0
Aggregations 0 0
Precedence 3072 3032
Variable Bound 0 0
Set Partitioning 0 0
Set Packing 0 0
Set Covering 1 1
Cardinality 0 0
Invariant Knapsack 1024 984
Equation Knapsack 0 0
Bin Packing 0 72
Knapsack 0 4248
Integer Knapsack 0 0
Mixed Binary 4320 0
General Linear 0 0
Indicator 0 0

Structure

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

value min median mean max
Components 0.7781512
Constraint % 0.0119947 12.0931 15.1134 15.1134
Variable % 4.3478300 18.2609 21.7391 21.7391
Score 0.4732280

Best Known Solution(s)

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
1 29 0 0 0 Ed Klotz 2019-11-15 Found using CPLEX 12.9

Similar instances in collection

The following instances are most similar to s1234 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
bnatt400 easy 3600 3600 0 0 5614 21698 Tatsuya Akutsu bnatt 1 benchmark binary benchmark_suitable precedence set_covering invariant_knapsack binpacking knapsack
bnatt500 hard 4500 4500 0 0 7029 27203 Tatsuya Akutsu bnatt Infeasible benchmark infeasible binary benchmark_suitable precedence set_covering invariant_knapsack binpacking knapsack
circ10-3 open 2700 2700 0 0 42620 307320 M. Winkler 280* binary decomposition precedence variable_bound set_partitioning set_packing invariant_knapsack knapsack mixed_binary
supportcase4 easy 3162 3162 0 0 9492 38036 Michael Winkler 0 binary feasibility benchmark_suitable aggregations precedence variable_bound invariant_knapsack knapsack mixed_binary
neos-2075418-temuka easy 122304 122304 0 0 349602 7610261 Hans Mittelmann neos-pseudoapplication-62 Infeasible benchmark infeasible binary benchmark_suitable precedence variable_bound set_covering invariant_knapsack knapsack

Reference

@inproceedings{DBLP:conf/asiacrypt/SunHWQMS14,
  author    = {Siwei Sun and
               Lei Hu and
               Peng Wang and
               Kexin Qiao and
               Xiaoshuang Ma and
               Ling Song},
  title     = {Automatic Security Evaluation and (Related-key) Differential Characteristic
               Search: Application to SIMON, PRESENT, LBlock, {DES(L)} and Other
               Bit-Oriented Block Ciphers},
  booktitle = {Advances in Cryptology - {ASIACRYPT} 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security,
               Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part
               {I}},
  pages     = {158--178},
  year      = {2014},
  crossref  = {DBLP:conf/asiacrypt/2014-1},
  url       = {http://dx.doi.org/10.1007/978-3-662-45611-8_9},
  doi       = {10.1007/978-3-662-45611-8_9},
  timestamp = {Mon, 10 Nov 2014 13:41:59 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/asiacrypt/SunHWQMS14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@misc{cryptoeprint:2014:747,
    author = {Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, Kai Fu},
    title = {Towards Finding the Best Characteristics of Some Bit-oriented Block Ciphers and Automatic Enumeration of (Related-key) Differential and Linear Characteristics with Predefined Properties},
    howpublished = {Cryptology ePrint Archive, Report 2014/747},
    year = {2014},
    note = {\url{http://eprint.iacr.org/2014/747}},
}

Last Update Mar 04, 2024 by Julian Manns
generated with R Markdown
© 2023 by Zuse Institute Berlin (ZIB)
Imprint