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's gravatar image

accept rate: 0%

edited 22 Jun '16, 03:36

Ehsan's gravatar image

Ehsan ♦

You have removed the constraints involving \(r\) and \(v\). What is the new objective?

(06 Oct '14, 13:54) Rob Pratt

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%20Pratt's gravatar image

Rob Pratt
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.


(25 Sep '14, 20:53) MGK

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 25 Sep '14, 04:36

Seen: 1,184 times

Last updated: 22 Jun '16, 03:36

OR-Exchange! Your site for questions, answers, and announcements about operations research.