As is well-known semidefinite relaxations of discrete optimization problems can
yield excellent bounds on their solutions. We present three examples from our
collaborative research. The first addresses the quadratic assignment problem and
a formulation is developed which yields the strongest lower bounds known for
larger dimensions. Utilizing the latest iterative SDP solver and ideas from
verified computing a realistic problem from communications is solved for
dimensions up to 512. These are so-called 2d QAPs and solving them exactly is
already challenging for dimensions of about 30 or more. In principle our
lower bounding techniques could be integrated into a branch&bound framework
but would be too expensive. When recently solving a previously unsolved 3d QAP
of dimension 16 exactly we thus resorted to integer programming techniques.
A strategy based on the Lovasz theta function is generalized to compute
upper bounds on the spherical kissing number utilizing SDP relaxations. Multiple
precision SDP solvers are needed and improvements on known results for all
kissing numbers in dimensions up to 23 are obtained. Finally, generalizing ideas
of Lex Schrijver improved upper bounds for general binary codes are obtained
in many cases.