# How to solve this optimization problem

 0 1 Definition: $$r_{kn} =\frac{1}{N} \log_2 ( 1 + p_{kn} h_{kn} )$$ $$S_{k} =\left\{ n \hspace{1mm}| \hspace{1mm}c_{kn}=1\right\}, \forall k$$ The Optimization Problem is: $$\displaystyle \underset{c_{kn}, p_{kn}} \min \sum\limits_{k=1}^{K} \sum\limits_{n=1}^{N}p_{kn}$$ Subject to $$\text{C1:}~{{{c}}_{kn}}\in \left\{ 0,1 \right\} \hspace{3mm}\left( \forall k,n \right)$$ $$\text{C2:}~{{p}_{kn}}\ge 0 \hspace{3mm}\left( \forall k,n \right)$$ $$\text{C3: }\sum\limits_{k=1}^{K}c_{kn}=1,\forall n$$ $$\text{C4:}~ \sum\limits_{n\in S_{k}} r_{kn} \ge R_{k}, \hspace{3mm}\forall k$$ asked 25 Sep '14, 04:36 MGK 13●4 accept rate: 0% Ehsan ♦ 4.8k●3●12●24 You have removed the constraints involving $$r$$ and $$v$$. What is the new objective? (06 Oct '14, 13:54) Rob Pratt

 3 You might consider combinatorial Benders decomposition, where the MILP master problem recommends values for c, and the NLP subproblem is your second formulation with c fixed. answered 25 Sep '14, 14:22 Rob Pratt 1.2k●2●6 accept rate: 28% Dear Rob, Thank you very much for your suggestion. Will you please formulate the master and slave programs fro this particular problem. MGK (25 Sep '14, 20:53) MGK 1 The NLP subproblem is your second formulation with $$c$$ fixed. The MILP master problem involves $$c$$, $$\eta$$, feasibility cuts, and optimality cuts, where the cuts are generated by solving the NLP subproblem. Explicitly, let $$F_j$$ be the support of $$c$$ in the $$j$$th feasibility cut, $$O_j$$ the support of $$c$$ in the $$j$$th optimality cut, $$v_j$$ the objective value in the $$j$$th optimality cut, and $$\overline{\eta}$$ an upper bound on the original objective value. Then the MILP master problem is to maximize $$\eta$$ subject to \begin{align} \sum_{k=1}^K c_{kn} &=1 && \forall n \\ \sum_{(k,n) \in F_j} (1 - c_{kn}) + \sum_{(k,n) \not\in F_j} c_{kn} &\ge1 && \forall j \in \mathcal{F} \\ \eta - (\overline{\eta} - v_j) \left(\sum_{(k,n) \in O_j} (1 - c_{kn}) + \sum_{(k,n) \not\in O_j} c_{kn}\right) &\le v_j && \forall j \in \mathcal{O} \\ c_{kn} &\in \{0,1\} && \forall k,n \end{align} The feasibility cuts prevent $$c$$ from taking values that yield an infeasible subproblem. The optimality cuts force the master objective value to be consistent with the objective value of the subproblem. (26 Sep '14, 12:05) Rob Pratt Dear Rob, Thank you very much for your effort. However, the slave problem is still NLP. The computational complexity is very high. Is there any way to make it less complex, for example some sort of approximation. Ans also to start with, we need to generate feasible starting point. How can I do that? (26 Sep '14, 23:27) MGK The success of Benders decomposition depends on the resulting subproblem being tractable once the complicating variables are fixed, and that's the situation I thought you were describing. The master problem I expressed is generic, but it turns out in this case that the feasibility cuts are unnecessary. For any given $$c$$, the trivial zero solution $$p=r=v=0$$ is feasible to the NLP subproblem. Do you have any data you can share? (26 Sep '14, 23:58) Rob Pratt Without incorporating stronger constraints into the master, this approach is correct but unlikely to work well since each new cut eliminates only one solution. On the other hand, for the problem data sent to me offline, the NLP relaxation of the original MINLP yields integer values for $$c$$. So maybe nothing fancy is needed here. (02 Oct '14, 10:17) Rob Pratt Dear Rob, thank you very much, what about the computational complexity of this solution? (03 Oct '14, 11:46) MGK showing 5 of 6 show 1 more comments
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190