1
$\begingroup$

I have a nonlinear mixed-integer optimization problem, and because of very high complexity when solving it using methods like Branch and Bound, I resorted to solve it using alternating method and continuous relaxation of the binary variables. So the issue is that the resulting optimum values are fractional. How to properly get binary values from the optimum fractional variables, such that the constraints in the problem remain satisfied?

For example, if $x$ is originally a binary variable $\{0,1\}$ and is linearly relaxed to be $0 \leq x \leq 1$, and I solved the optimization problem based on this relaxed constraint. If the problem is finished and the optimum solution is in the continuous range $[0,1]$ not binary, and I want to properly binarize it, keeping the problem still feasible (i.e. the binarization should not affect the problem feasibility). The Constraints are that in the attached image The Constraints are that in the attached image

$\endgroup$
6
  • 1
    $\begingroup$ This can't be done in general, but for some particular problems, a rounding procedure (or possibly a randomized rounding procedure that might round to 0 or 1 with probabilities depending on the fractional value of the variable) may be possible. If you tell us more about your specific problem and its constraints, we might be able to help. $\endgroup$ Aug 5 at 4:08
  • $\begingroup$ @BrianBorchers Thank you for your trying to help. The problem is about maximizing the sum throughput in a communication system by optimizing the users assignment (Alphas) and the per-channel power allocation indicators (Betas). The constraints are in the attached image. I have edited the post. $\endgroup$ Aug 5 at 12:42
  • $\begingroup$ You could simply round down all of the fractional $\alpha$ and $\beta$ values to 0 and get a feasible solution, but that wouldn't be very interesting... $\endgroup$ Aug 5 at 15:57
  • $\begingroup$ @BrianBorchers Yes, this will cancel the whole problem. $\endgroup$ Aug 6 at 4:27
  • $\begingroup$ A simple heuristic would be to sort the values of $\alpha$ and $\beta$ from largest to smallest and then add ones from this list as long as they don't violate any constraints. $\endgroup$ Aug 6 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.