  The central object of this PhD thesis is known under different names in the
fields of computer science and statistical mechanics. In computer science, it
is called the Maximum Cut problem, one of the famous twenty-one Karp's original
NP-hard problems, while the same object from Physics is called the Ising Spin
Glass model. This model of a rich structure often appears as a reduction or
reformulation of real-world problems from computer science, physics and
engineering. However, solving this model exactly (finding the maximal cut or
the ground state) is likely to stay an intractable problem (unless $\textit{P}
= \textit{NP}$) and requires the development of ad-hoc heuristics for every
particular family of instances.
  One of the bright and beautiful connections between discrete and continuous
optimization is a Semidefinite Programming-based rounding scheme for Maximum
Cut. This procedure allows us to find a provably near-optimal solution;
moreover, this method is conjectured to be the best possible in polynomial
time. In the first two chapters of this thesis, we investigate local non-convex
heuristics intended to improve the rounding scheme.
  In the last chapter of this thesis, we make one step further and aim to
control the solution of the problem we wanted to solve in previous chapters. We
formulate a bi-level optimization problem over the Ising model where we want to
tweak the interactions as little as possible so that the ground state of the
resulting Ising model satisfies the desired criteria. This kind of problem
arises in pandemic modeling. We show that when the interactions are
non-negative, our bi-level optimization is solvable in polynomial time using
convex programming.
