Determining direction of unboundedness
Sarah Root
my model, and I cannot figure out why. I would like to understand the
direction in which my model is unbounded, but have been unable to
extract this information. In googling and searching this group, I
found references to an unbdd suffix, but I cannot get that to work --
it says that such a suffix does not exist.
The core problem is due to the linearization of an absolute value
whose value I would like to maximize. I have tried several ways of
linearizing the problem, all of which appear to make the problem
unbounded.
I am able to get this output from CPLEX
ILOG CPLEX 10.000, licensed to "university-fayetteville, ar", options:
e m b q p=2
CPLEX 10.0.0: rays 3
Dual infeasible due to empty column 'x1744'.
CPLEX 10.0.0: integer infeasible or unbounded in presolve.
0 MIP simplex iterations
0 branch-and-bound nodes; no basis.
...but I do not have a variable named x1744 so it is tough to figure
out what this means.
When I turn off presolve, I get this output, which is also not telling
me the direction in which the solution is unbounded.
ILOG CPLEX 10.000, licensed to "university-fayetteville, ar", options:
e m b q p=2
CPLEX 10.0.0: presolve 0
CPLEX solution status 118 with fixed integers:
integer unbounded ray
CPLEX 10.0.0: integer unbounded ray; objective Infinity
0 MIP simplex iterations
0 branch-and-bound nodes
Status recovering solution: integer unbounded ray; no basis.
Any thoughts? I would be happy to post my model if this would help to
clarify this issue that I describe.
Thanks,
Sarah
Sarah Root
Paul
On Oct 17, 11:00 am, Sarah Root <sarahr...@gmail.com> wrote:
> I have a problem that is unbounded because of the way that I express
> my model, and I cannot figure out why. I would like to understand the
> direction in which my model is unbounded, but have been unable to
> extract this information. In googling and searching this group, I
> found references to an unbdd suffix, but I cannot get that to work --
> it says that such a suffix does not exist.
Try option relax_integrality 1; to solve the LP relaxation. That
should give you the .unbdd suffix for your variables. It will tell
you a recession direction, but not necessarily one containing integer
lattice points (I think). Still, knowing any recession direction
should point you in the right, er, direction.
> The core problem is due to the linearization of an absolute value
> whose value I would like to maximize. I have tried several ways of
> linearizing the problem, all of which appear to make the problem
> unbounded.
The usual way of linearizing |x| is to write x = x1 - x2 and |x| = x1
+ x2 with x1 and x2 >= 0. That won't work if you're maximizing |x|.
Assuming you have apriori bounds -M0 <= x <= M1 (M0 and M1 positive),
you can introduce a binary variable y and constraints x1 <= M1*y, x2
<= M0*(1-y).
> Any thoughts? I would be happy to post my model if this would help to
> clarify this issue that I describe.
If the above doesn't help, you might want to post the model.
/Paul