Originally posted by: gangulo

Suppose that we have a problem in variables (x,y), where x is integer and y is continuous. If (x*,y*) is an optimal solution, then y* is optimal given x*. Now, when CPLEX finds a new incumbent (x,y), is it true that y is optimal given x? That should be the case when (x,y) comes from an integral node of the tree, but I'm not sure whether the same holds when (x,y) is found by an heuristic. Any idea?

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> gangulo wrote:
> Suppose that we have a problem in variables (x,y), where x is integer and y is continuous. If (x*,y*) is an optimal solution, then y* is optimal given x*. Now, when CPLEX finds a new incumbent (x,y), is it true that y is optimal given x? That should be the case when (x,y) comes from an integral node of the tree, but I'm not sure whether the same holds when (x,y) is found by an heuristic. Any idea?
>
> Thanks!
I think it depends on the heuristic. Many heuristics involve starting at a node LP,
then fixing some integer variables and reoptimizing the LP. I think in those cases
your condition will hold, for essentially the same reason it holds when a new
incumbent is found by branching. But, I'm less clear on whether this holds for
heuristics that solve MIP subproblems rather than LP subproblems. In that case the
MIP subproblem may stop with a feasible but sub-optimal integer solution that
improves upon the incumbent. And then you have genetic algorithm type heuristics
that combine solutions without solving any subproblem at all; those probably have
more potential to violate the property in question.

I don't think it's worth a careful analysis of all the CPLEX heuristics to try
to answer this question, even though it might be interesting to do so. Even if
we found that this was true as of CPLEX 12.5, it could change in the future as long
as it is theoretically possible for a heuristic solution to violate this property.
However, if you need this property to hold for all solutions you get from CPLEX,
I think you can accomplish that by solving the associated fixed LP for each
solution of interest. When you fix the integer variables at the solution value and
solve the LP, the resulting solution will satisfy this property. You could also
use this approach as an ad hoc test to at least empirically try to answer this
question. But, there's no guarantee, regardless of how many models you run, that
the solutions you generate will cover all of CPLEX's heuristics.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: gangulo

Thanks for replying Ed! As you said, I can fix x and optimize over y. I just wanted to know if it was possible to skip that ;)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> gangulo wrote:
> Thanks for replying Ed! As you said, I can fix x and optimize over y. I just wanted to know if it was possible to skip that ;)

I'll be curious to see if you encounter any heuristic solution where the fixed problem
yields a significantly better objective.
#CPLEXOptimizers
#DecisionOptimization