Skip to main content

Getting "DUAL_INFEASIBLE" when solving a very simple linear programming problem.

Answered

Comments

1 comment

  • Eli Towle
    • Gurobi Staff Gurobi Staff

    If you set the InfUnbdInfo parameter, Gurobi will supply you with an unbounded ray that proves the model is infeasible. You can query this ray by examining the UnbdRay attribute of each Var object.

    However, it's easy to construct an unbounded ray for this model by looking at its structure. The model is of the following form:

    $$\begin{alignat}{2} \max_{\phi,\gamma}\ & \phi && \\ \textrm{s.t.}\ & \sum_{i \in S^+} a_i \gamma_i &- \sum_{i \in S^-} a_i \gamma_i + \phi &\leq c \\ && \gamma_i &\leq 0 \quad i = 1, \ldots, 574. \end{alignat}$$

    where \( S^+ \) and \( S^- \) are disjoint nonempty subsets of \(\{1, \ldots, 574 \}\), \( c > 0 \), and \( a_i > 0 \) for all \( i \in S^+ \cup S^- \).

    Let \( k \in S^+ \). Consider any \( M > 0 \). We can construct a feasible solution to this model with objective value \( M \) as follows:

    $$\begin{alignat*}{2} \phi &= &&M \\ \gamma_k &= -&&M / a_k \\ \gamma_i &= &&0 \qquad\quad i = 1, \ldots, k-1, k+1, \ldots, 574. \end{alignat*}$$

    For example, with \( k = 1 \) (\(\gamma_1 = 0.396\)), the following solution is feasible for all \( M > 0 \):

    $$\begin{alignat*}{2} \phi &= &&M \\ \gamma_1 &= -&&M / 0.396 \\ \gamma_i &= &&0 \qquad\qquad\quad i = 2, \ldots, 574. \end{alignat*}$$

    Thus, the model is unbounded.

    Have you tried writing out an LP file and examining it? Perhaps this model is not formulated as you expect. For example, the \( c \) variables and many \( \gamma \) variables do not show up in the objective function or any constraints.

    0

Please sign in to leave a comment.