paper-packing

Materials regarding the paper packing project, proving that exactly 1038 sheets of A10 fit into one A0 orthogonally.

Links

• YouTube video about this project: youtu.be/zDKBCIMkDbw
• Library of Papel: noel-friedrich.de/papel/
• Fun Orthogonal Rectangle Packing Website: noel-friedrich.de/forp/

Lower Bound

The lower bound is proven by giving an arrangement of 1038 sheets of A10 in a single A0. The packing is avaiable as a .txt file here and as an image (vector graphic here).

Upper Bound

The optimal weights for the (1189, 841, 37, 26) instance can be found at upper-bound/weights.

The code used for generating this large weightmap can be found at upper-bound/weight-generation/large-lp.

Smaller Weight Generation

To compute the optimal weights for smaller instances locally, there also exists a smaller command line utility available at upper-bound/weight-generation/smaller-lp/generate_weights.py. Note that the utility requires the python packages Pillow, numpy, matplotlib and gurobipy to be installed. Additionally, Gurobi must be installed on the machine. Here is the help output for the utility program used to create smaller weightmaps:

usage: generate_weights.py [-h] [-o OUT_IMG] [-w OUT_WEIGHTS] [-r] [-v] [-s {simplex,barrier,pdhg}] L W a b

Generate an optimal weighing pattern by solving an LP using Gurobi

positional arguments:
  L                     Height of larger rectangle
  W                     Width of larger rectangle
  a                     Height of smaller rectangle
  b                     Width of smaller rectangle

options:
  -h, --help            show this help message and exit
  -o OUT_IMG, --out-img OUT_IMG
                        Path of the weightmap image (.png) to be outputted
  -w OUT_WEIGHTS, --out-weights OUT_WEIGHTS
                        Path of the weightmap weights (.npy) to be outputted
  -r, --disable-rotation
                        If set, rotated smaller rectangles (90°) won't be considered
  -v, --verbose         If set, Gurobi's log will be outputted to stdout
  -s {simplex,barrier,pdhg}, --solver {simplex,barrier,pdhg}
                        Solver that Gurobi uses to solve the LP

A(m) in A(n)

Upper and lower bound proofs for A(m) in A(n) can be found here. Here is a table of all relevant directories:

	A0	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
A0	A0 in A0	A1 in A0	A2 in A0	A3 in A0	A4 in A0	A5 in A0	A6 in A0	A7 in A0	A8 in A0	A9 in A0	A10 in A0
A1		A1 in A1	A2 in A1	A3 in A1	A4 in A1	A5 in A1	A6 in A1	A7 in A1	A8 in A1	A9 in A1	A10 in A1
A2			A2 in A2	A3 in A2	A4 in A2	A5 in A2	A6 in A2	A7 in A2	A8 in A2	A9 in A2	A10 in A2
A3				A3 in A3	A4 in A3	A5 in A3	A6 in A3	A7 in A3	A8 in A3	A9 in A3	A10 in A3
A4					A4 in A4	A5 in A4	A6 in A4	A7 in A4	A8 in A4	A9 in A4	A10 in A4
A5						A5 in A5	A6 in A5	A7 in A5	A8 in A5	A9 in A5	A10 in A5
A6							A6 in A6	A7 in A6	A8 in A6	A9 in A6	A10 in A6
A7								A7 in A7	A8 in A7	A9 in A7	A10 in A7
A8									A8 in A8	A9 in A8	A10 in A8
A9										A9 in A9	A10 in A9
A10											A10 in A10

• Lower bounds are given as arrangement files that can be loaded into noel-friedrich.de/forp as .txt files.
• Upper bounds are given as short descriptions contained in appropriate .txt/ or .md files.

Table of proven values

	A0	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
A0	=1	=2	=4	=8	=16	=32	=64	=128	=258	=516	=1038
A1		=1	=2	=4	=8	=16	=32	=64	=129	=258	=518
A2			=1	=2	=4	=8	=16	=32	=64	=128	=258
A3				=1	=2	=4	=8	=16	=32	=64	=129
A4					=1	=2	=4	=8	=16	=32	=64
A5						=1	=2	=4	=8	=16	=32
A6							=1	=2	=4	=8	=16
A7								=1	=2	=4	=8
A8									=1	=2	=4
A9										=1	=2
A10											=1

• the first line of this table is documented as sequence A395145 on the On-Line Encyclopedia of Integer Sequences.