I was wondering if there's some classes of combinatorial problems (specifically assignment problems) something like maximize:
$$ f(\vec{x}) = \sum_{i,j} x_{i}x_{j}2^{i+j}, \;\; x_i \in {0,1} \;\;\forall i$$
My example is trivial... just set each $x_i = 1$, but in such a case I would firstly "guess" the solution and then prove that such solution is correct.
But except methods that involves the use of a computer (as far as I know most of these problems are solved by algoritms) are there cases where one could actually solve the problem without a computer?
$f(\vec{x}) = \sum_{i,j} x_{i}x_{j}2^{i+j}, \;\; x_i \in {0,1}$, can be generalized into $f(\vec{x}) = \sum_{i,j} a_{i,j}x_{i}x_{j}$ where the $a_{i,j}$ are the coefficient of a symmetric matrix $A$, and where the $x_i$ take any real value. It is what is called a quadratic form, with matrix notation $X^TAX$ ($X$ is nothing else than $\vec{x}$.)
It is known that the Rayleigh quotient $R(\vec{x}) = \dfrac{X^TAX}{X^TX}$, $X \neq 0$, for any $X$, https://en.wikipedia.org/wiki/Rayleigh_quotient takes all its values in the closed interval $[\lambda_{min}, \lambda_{max}]$ (minimum and maximum eigenvalues of matrix $A$).
This can provide a way to obtain the maximum of $X^TAX$ when $X$ has components $0$ or $1$, by screening the values of all the $R(\vec{x})$ ($2^n-1$ values) if $n$ is not very large (say $n < 20$).
If matrix $A$ has a particular structure, such as block-diagonal, these computations can be accelerated...