1
$\begingroup$

Suppose, there is mixed-integer programming as follows:

$(1)$ $$\begin{aligned} \min&\quad c^{\top} x\\ \text{s.t.}& \quad A x \geq b \\ &\quad B x \geq d \\ &\quad x \geq 0 \\ &\quad x_{j} \in \mathcal{Z}, j \in I \end{aligned}$$

Where $I$ is an index set contained in $\{1,\cdots,n\}$. Defining:

$(2)$ $$ \Gamma:=\left\{x \in \Re^{n} \mid B x \geq d, x \geq 0, x_{j} \in \mathcal{Z}, j \in I\right\} $$ Based on the Mixed-integer finite basis theorem, if $\Gamma$ is given by above set, there exists $x^1,\cdots,x^r$ such that:

\begin{equation} \operatorname{conv}(\Gamma)= \left \{x \in \Re^{n} \mid x=\sum_{i=1}^{q} z_{i} x^{i}+\sum_{i=q+1}^{r} z_{i} x^{i},\right. \ \left.\sum_{i=1}^{q} z_{i}=1, z_{i} \geq 0, i=1, \ldots, r\right\}. \end{equation}

Also, the convex hull relaxation of the original problem is in the following form:

$(3)$ \begin{equation} \begin{array}\\ \min & c^{\top} x & \\ \text { s.t. } & A x \geq b & \\ & x \in \operatorname{conv}(\Gamma) \end{array} \end{equation}

In order to the above definitions, I would like to know:

  1. What are exactly integer variables defined based on the model $(1)$ and definition $(2)$?
  2. Why the constraint $Ax \geq b$ should be omitted from the definition $(2)$, but should be incorporated into the $(3)$?

P.S: Actually, the concept is based on Dantzig-Wolfe decomposition to re-formulate the (mixed-integer) linear programming to the equivalent problem that can be represented as the combination of the extreme points and extreme rays. After that, solving this master problem by Lagrangian dual approach. For linear programming, the approach is somewhat straightforward, but when some of the variables should be integer understanding the above definitions is a bit challenging.

$\endgroup$
8
  • $\begingroup$ Some additional detail would be helpful, starting with a citation for the "mixed-integer finite basis theorem". Also, are $x^i\in \Gamma$, and what distinguishes $x^1,\dots,x^q$ from $x^{q+1},\dots,x^r$? $\endgroup$
    – prubin
    Nov 6 '21 at 16:11
  • $\begingroup$ @Prof. Rubin, Many thanks for your attention. For citation please, see this link. For the second part of your question, $x^i \in \Gamma$ and other concepts are what I am trying to know. Also, $x^1,\dots,x^q$, if I understand correctly(!) referred as the extreme points and the rest referred as the extreme rays. $\endgroup$
    – A.Omidi
    Nov 6 '21 at 20:38
  • 1
    $\begingroup$ The link, unfortunately, only shows the first two pages of the chapter, and not the statement of the theorem. I found what may or may not be the same theorem (definitely the same name) here (slide 10), but it assumes rational constraint matrices. Are you assuming that $B$ and $d$ contain exclusively rational numbers? $\endgroup$
    – prubin
    Nov 9 '21 at 21:18
  • $\begingroup$ @prubin, Many thanks professor. First, I am sorry for the provided link. Please, see this link that contains the whole chapter. Unfortunately, I could not see any phrase "rational" in this chapter. But w.r.t the fact that the author of both resources is the same person and either, in the chapter the author might have pointed out this without further explanation, I think what you mentioned should be true. By this assumption, is it possible to answer the questions? $\endgroup$
    – A.Omidi
    Nov 10 '21 at 7:46
  • 1
    $\begingroup$ It means that the components of $A$ and $b$ are rational numbers (integers or fractions). $\endgroup$
    – prubin
    Nov 13 '21 at 16:17

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.