3
$\begingroup$

I am working on a unit commitment problem where I need to turn the constraints to dual. But the constraints do not deal with the same time period which makes dual process confusing. for a simple example:

$min \sum_{t=1}^T(Cx(t))$

$s.t.$

$ \quad x(t) \ge LB, -x(t) \ge -UB,\quad \forall t$

$ \quad x(t)-x(t-1) \ge -RD,\quad 1< t \le T$

$ \quad x(1) \ge -RD+x(0),\quad \quad t = 1$

$ \quad x(t) = D(t),\quad \forall t$

where $x(t)$ is the only variable here and $x(0)$ serves as a known initial condition. and below is my dual form of the problem and the $ \lambda_1(t),\ldots,\lambda_5(t)$ represent the dual multiplier of the above constraints. Note: for simplification, I ignore the units number here.

$max \sum_{t=1}^T(LB*\lambda_1(t))+\sum_{t=1}^T(-UB*\lambda_2(t)) + \sum_{t=2}^T(-RD*\lambda_3(t)) +(-RD+x(0))*\lambda_4+ \sum_{t=1}^T(D(t)*\lambda_5(t))$

$s.t.$

$ \quad\lambda_1(1) -\lambda_2(1) - \lambda_3(1) + \lambda_4 + \lambda_5(1) \le C$

$\quad \lambda_1(t) -\lambda_2(t) - \lambda_3(t) + \lambda_3(t-1) + \lambda_5(t) \le C, \quad 2 < t < T $

$\quad \lambda_1(T) -\lambda_2(T) + \lambda_3(T) + \lambda_5(T) \le c$

In most of the paper I read, authors either just ignore the initial condition or just use the second dual constraints above without consider the boundary of the constraints. The reason I write the constraints this way is that, for example, $T=4$ the third constraint can be found like the matrix below.

$\begin{bmatrix}-1&1&0&0\\0&-1&1&0\\0&0&-1&1\end{bmatrix}$

Is my formulation correct? or is there any more common mathematical representation of this type of problem? any advice will be appreciated! And sorry for poor English.

$\endgroup$
2
  • 1
    $\begingroup$ I am new to OR but not to stats or engineering . What is RD ? I got that LB / UB are lower/upper bounds $\endgroup$ Sep 12 '21 at 22:09
  • $\begingroup$ @WestCoastProjects it represents "Ramp Down" but I assume it is a not common sense in OR, so don't worry $\endgroup$
    – Lee Adolin
    Sep 13 '21 at 5:50
3
$\begingroup$

You're close, but your indexing is off in the middle dual constraint. I assume you mean $t\ge 2$ rather than $t>2$ in the second dual constraint (and that $c$ is $C$ in the last one). Keep in mind that $x(\tau)$ appears in the third primal constraint with coefficient +1 when $t=\tau$ and in with coefficient -1 when $t=\tau+1$, not when $t=\tau-1$ and $t=\tau$ respectively.

$\endgroup$
3
  • $\begingroup$ Thanks you so much sir! I do make a typo in the middle dual constraint it should be 2<= t <= T. But I am a little confused about the second statement about the third primal constraint, shouldn't it be the same? $\endgroup$
    – Lee Adolin
    Sep 13 '21 at 7:51
  • $\begingroup$ I'd like to ask if this representation is acceptable in your understanding since I find most of paper doesn't explicitly do so, but it does make a big difference on practice. $\endgroup$
    – Lee Adolin
    Sep 13 '21 at 7:51
  • 1
    $\begingroup$ Try writing out all the primal constraints of a small example (say $T=3$), associate a dual variable with each primal constraint, and then see what the dual constraints look like. Hopefully that will help. I don't know what you mean about "representation". The way you wrote your dual constraints looks fine to me; I just think there are errors in the middle one. $\endgroup$
    – prubin
    Sep 13 '21 at 15:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.