Error: Dual/Infeasible Linear Program - Not making sense
The following is an example where I get errors:
https://www.dropbox.com/sh/weljct2fepvz3o9/AAAwgBCVoVz_C9z72ETtU_h1a?dl=0
(where Q=A from the notation below)
I want to solve the following problem:
min_{X, t} t
such that
AX=x+t*d
and X_L<X<X_U
where X_L, X_U, A (matrix), x (vector), d (vector) are given. To solve this problem I take "td" to the LHS and add "-d" as a column to A and solve for an additional unknown on LHS: 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.
One interesting thing 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.
Any help will be much appreciated.
-
Hi Faraz,
I am guessing (since you did not provide an MPS or LP) that you expect any finite number not to be infinity, whereas any bound around 1e20 is already considered as infinity (see the bound attribute documentation), so for sure, a problem with very large bounds can be considered unbounded
0 -
Hi Daniel,
I am using the R module and here is the code. It is quite simple:
d = -1*dA = cbind(A, d)model <- list()model$A <- Amodel$rhs <- xmodel$sense <- c('=')model$obj <- c(rep(0,ncol(A)-1),1)model$modelsense <- 'min'model$ub <- c(X_U,Inf)model$lb <- c(X_L,-Inf)result <- gurobi(model,params = list(OutputFlag=1))return(result$objval)As you said, I am setting the bounds on "t" to be -Inf and Inf.Qs: Is Gurobi's error of infeasibility wrong when I set DualReductions parameter to equal 0?Qs: What should I do then? I was trying to compute the lower bound on "t" using this program. Do I have to make the bounds on "t" finite? Is that the only solution? If so, is there any guideline for this as to what bounds to use?EDIT: Forgot to add that some instances of this code (i.e. different A, x, X_l, X_U and d) as its written work perfectly fine.1 -
Have you tried
gurobi_write(model, 'mymodel.mps');
gurobi_write(model, 'mymodel.lp');
The MPS model is a binary compatible format (but hard to read), LP format is easy to read (but not 100% accurate in terms of number representation). You should take a look
You can always call gurobi_iis on infeasible models, or you can use the parameter http://www.gurobi.com/documentation/8.1/refman/infunbdinfo.html#parameter:InfUnbdInfo
0 -
Hi Daniel,
I have added the mps and lp file to the dropbox link in the original post. What is confusing me is the following:
Gurobi says that the model is infeasible. Yet gurobi is able to find a solution to the constraints (for example, change the objective in the mps file to 0). This is replicable with the the mps file I am providing. So how can the model be infeasible?
I am assuming it is not unbounded because using DualReductions=0 tells me that it is an infeasibility issue.
Can you take a look at the mps file?
0 -
Hi Faraz,
Sorry for the delay, I was out the last few days. the MPS and LP file you posted have zero objective functions, and Gurobi does find a feasible solution for both of them.... I guess you did not send a version with the objective.
What __could__ happen is that the problem is unbounded (with the non-trivial objective) but that Gurobi decides to solve the dual problem instead (and that one should be infeasible if the primal is unbounded). Still, having the model that triggers the issue is the only way to be sure what is going on. By the way, I assume you are using v8.1.1?
Best,
Daniel
0
Please sign in to leave a comment.
Comments
5 comments