Implications of Integral linear program
In general, this is not possible unless P=NP. So, it is unlikely that such a method exists.

Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $C_i$ and variables $v$. For each clause, denote the variables that appear positive by $C_i^+$ and the variables that appear negative by $C_i^-$. Now, consider the following integer program $P$:

$\begin{align} 
\max 1 \quad \text{s.t.} \quad &amp; \sum_{v\in C_i^+} x_v + \sum_{v\in C_i^-} (1-x_v) \geq 1 \text{ for all } i\\
&amp; x_v \in \{0,1\} \text{ for all } v
\end{align}$

Note that $P$ has a feasible solution if and only if our 3SAT instance is satisfiable. (a solution to $P$ corresponds to a satisfying assignment of the 3SAT instance) This solution is then 'optimal' as well, as all feasible solutions of $P$ have the same cost. This means that also the relaxation $P^*$ must have the same cost if $P$ is feasible. So, we will assume that the given 3SAT instance is satisfiable, so that the costs of $P$ and $P^*$ are equal.

Now, suppose we have some method to find a solution for $P$ from a solution $y\in [0,1]^d$ for $P^*$. As $P^*$ is a normal linear program, we can find such a solution $y$ in polynomial time, by using e.g. the ellipsoid method. Then, our method gives us a solution for $P$ in polynomial time. But this solution gives a satisfying assignment for our initial 3SAT problem, which means we can find a satisfying assignment to 3SAT problems in polynomial time. As finding a satisfying assignment for 3SAT is NP-hard (even if we know the instance has a satisfying assignment), this means that P=NP



I suppose that intuitively, what is going on here is that knowing the value of a solution to an integer program does not tell you a lot about the specific variable assignment. In a way, this is because the 'complexity' of a linear program lies mostly in its constraints, rather than the goal function.