Linear Program is Surprisngly Infeasible - Trying to Write the Dual

I need to solve the following linear program:

$$\displaystyle{\min_{\bar{X},t}} \hspace{0.1in}t$$

such that: $$A\bar{X}=\tilde{x} + td$$

where $$A$$ is $$N\times N$$ and known, $$t$$ is scalar, $$\tilde{x}$$ is a known $$N\times 1$$ vector, $$d$$ is a known $$N\times 1$$ vector and $$\bar{X}$$ lies in the set $$\mathcal{X}$$ where: $$\mathcal{X}=\{X | \underline{X} and $$\overline{X}$$ and $$\overline{X}$$ are known $$N\times 1$$ vectors.

To solve this I am essentially taking the $$td$$ to the left hand side, adding $$-d$$ as a column to the given A and adding $$t$$ as an additional unknown on the LHS.

The problem is that when implementing this in Gurobi, I get the error that the problem is infeasible or unbounded. Removing gurobi's DualReduction approximation gives us that the algorithm is infeasible.

I was thinking about writing the dual problem and figuring out if the issue becomes more apparent there, but I am unable to do so. Can anyone help me figure out how to write the dual problem?

Example:

https://www.dropbox.com/sh/weljct2fepvz3o9/AAAwgBCVoVz_C9z72ETtU_h1a?dl=0

X_L file corresponds to $$\underline{X}$$ and X_U file corresponds to $$\overline{X}$$. Q file corresponds to $$A$$ in the notation above. $$x$$ corresponds to $$\tilde{x}$$.

When I use lpSolve in R for this problem, I get weird solutions that are not within the bounds (I use -Inf and Inf as bounds for $$t$$).

When I use gurobi, it gives me a unbounded or infeasbile error. If I set DualReductions=0 (link), it says that the model is infeasible. However, if I solve this system with the objective set to 0, I get a solution. Again the bounds on $$t$$ are set to -Inf and Inf.

Therefore I am very confused as to what is happening with this problem. Is this problem infeasible? If so, then how come setting objective equal to 0 produces solutions? If not, then why won't gurobi or lpSolve work?

• If you really have numbers such as 1e-17 in your linked data then you could start by clearing this up. Perhaps your solver is getting into numerical issues. – Michal Adamaszek May 14 at 12:21
• @MichalAdamaszek In these scenarios is it reasonable to round? This linear program is called within a coordinate descent procedure. Would approximations/rounding mess this up? One interesting thing that I am finding is that if I change the bounds for $t$ to something like -10k to 10k, then solutions are produced. These solutions are insensitive to the bounds. So for example, -1000 and 1000 gives same solution. But -Inf and Inf produces errors. – user52932 May 14 at 16:13
• All I know is that if a feasibility problem is feasible/infeasible, while adding an objective makes it otherwise, then numerical issues are to blame. For example, it may be that the expected solution is huge. – Michal Adamaszek May 14 at 20:22
• Are you sure your LP is properly conditioned? – Rodrigo de Azevedo May 18 at 18:39
• Why not post your solver's output in your question? – Rodrigo de Azevedo May 18 at 18:40