Relaxation of the binary optimization problem doesn't make sense in terms of the original problem - how do I repose the model to make sense?

Question

Suppose I have a set of binary variables $x\in \{0,1\}^N$, where in the context of my optimization problem these binary parameters mean to include the parameter in a model or not include it, where there is a total of $N$ parameters. If one was to solve this problem using the standard techniques of integer programming, i.e., continuous relaxation $0 \leq x \leq 1$, I arrive at a troublesome point because the relaxation of the variable (which means include or not include) makes no sense (I can't include $\frac{3}{4}$ of a parameter in the model).

This seems like a problem that many would inevitably run into, so I was curious how people would resolve this problem. The only way seems to reformulate the model, but I'd be very curious if someone could give insight.

Thank you.

Answer 1

For integer programming, solving the continuous relaxation is only the first step. To find an optimal integer solution, the branch and bound algorithm is commonly used. For binary variables, one approach to obtain an integer feasible solution from an optimal continuous relaxation is to apply randomized rounding, where the value of the variable is treated as the probability that the variable takes value $1$.