0
$\begingroup$

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} <X < \overline{X}, X \in \mathbb{R}^N\}$$ 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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michal Adamaszek May 14 at 12:21
  • $\begingroup$ @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. $\endgroup$ – user52932 May 14 at 16:13
  • $\begingroup$ 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. $\endgroup$ – Michal Adamaszek May 14 at 20:22
  • $\begingroup$ Are you sure your LP is properly conditioned? $\endgroup$ – Rodrigo de Azevedo May 18 at 18:39
  • $\begingroup$ Why not post your solver's output in your question? $\endgroup$ – Rodrigo de Azevedo May 18 at 18:40

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.