Given a set of rectangles and a rectangular container
with a fixed width, called a strip,
the two-dimensional strip packing problem (2SP)
requires all the given rectangles to be placed
orthogonally without overlap within the strip
so as to minimize the height of the strip.
2SP and its variants have
many applications in steel and textile industries,
and it has indirect application in scheduling problems.
However, 2SP is known to be NP-hard.
In this paper, we propose an exact algorithm to 2SP with and without rotations of 90 degrees,
which consists of following three algorithms.
First one is a branch-and-bound algorithm to the 2SP with fixed height problem (2SPFH),
a decision problem of 2SP which asks whether
there is a feasible placement of all rectangles within
the strip with fixed width and height.
Second one is a heuristics to 2SPFH, which is based on a branch-and-bound method
with a heuristic restriction of the search space.
Third one is a branch-and-bound algorithm
to the one-dimensional contiguous bin packing problem (1CBP)
with fixed height (1CBPFH),
which is a relaxation problem of 2SPFH.
To reduce the search space in the three algorithms,
we introduce several new ideas.
We define a canonical form of feasible solutions for 2SP and 1CBP
and limit the search space to look for just a canonical solution.
We also derive a new lower bound on the optimal value to 2SP
by relaxing the problem to PARTITION,
an NP-hard optimization
problem which can be solved in a
practical time by dynamic programming.
We conducted experiments using benchmark instances
and observed that our algorithm is competitive with the other algorithms.
Our algorithm succeeded to find the optimal values
for most of the instances in a practical time.
Especially, we found that the optimal values of instances
"gcut02" and "cgcut02" (without rotations) are 1187 and 64,
respectively, which have not been
known by any of the other existing algorithms.