メインコンテンツへスキップ

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

回答済み

コメント

2件のコメント

  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Eli Towle
    • 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

投稿コメントは受け付けていません。