Originally posted by: SystemAdmin

[Student said:]

Hi,

I need some help with the Cplex Heuristic Callback,
more exactly with the function setSolution.

In my Heuristic Callback, I create an Integer feasible solution
for which I can guarantee it is feasible for the MIP I want to solve.
But when I try to pass my solution to CPLEX with setSolution, it simply ignores it.
It does not use my solution even though it is better than the current incumbent.

I have two assumptions, why it may not work, but I don't know how to make it work.
The first reason could be that my MIP has three kinds of variables: boolean, integer and real variables,
which are stored in multidimensional BoolVarArrays, IntVarArrays and NumVarArrays.
I copy them altogether in a onedimensional NumVarArray to pass them to setSolution.

Could this be a reason, why it doesn't work?
By the way, does the solution I provide have to be complete,
that means, do I have to give a solution value to all the Variables in my model?

The second reason could be that my solution is not connected to the node at which the Heuristic Callback
is called. That means, there can be variables which have their values already fixed at that node,
but the solution I want to pass to CPLEX gives them another value.
Or the bounds at that node in the tree are violated by my solution.

What I need is a possibility to pass arbitrary solutions for my MIP to CPLEX at any node the Heuristic Callback is called.

Thank you for your help!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=Student link=topic=824.msg2465#msg2465 date=1231601068]
I have two assumptions, why it may not work, but I don't know how to make it work.
The first reason could be that my MIP has three kinds of variables: boolean, integer and real variables,
which are stored in multidimensional BoolVarArrays, IntVarArrays and NumVarArrays.
I copy them altogether in a onedimensional NumVarArray to pass them to setSolution.
Could this be a reason, why it doesn't work?


That is the correct approach.  There should be no problem with mixing integer, boolean and general numeric variables in one array.

[quote author=Student link=topic=824.msg2465#msg2465 date=1231601068]
By the way, does the solution I provide have to be complete,
that means, do I have to give a solution value to all the Variables in my model?


I believe so.  When you feed an initial incumbent to CPLEX at the outset of a run, it does not have to be complete; CPLEX will take a partial solution and try to complete it.  In a (an?) heuristic callback, though, I believe you have to supply a complete solution.  I think the documentation might be a bit clearer about this, but it does say "all variables" in one spot.

[quote author=Student link=topic=824.msg2465#msg2465 date=1231601068]
The second reason could be that my solution is not connected to the node at which the Heuristic Callback
is called. That means, there can be variables which have their values already fixed at that node,
but the solution I want to pass to CPLEX gives them another value.
Or the bounds at that node in the tree are violated by my solution.


I don't think that's a problem.

/Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[Student said:]

Hi Paul,
Thank you for your answer!

So I can rule out two possible causes for my problem.
I definitely know that the solution I want to provide is feasible for my
problem as in the Heuristic Callback I have (as a test) created a copy of my
model to a new Cplex-Object together with the variables fixed at my solution values
and it shows to be feasible and it has the correct objective value for my solution.
(But when I use setBounds() to fix the variables to those solution values and use solve()
inside the Callback to resolve the node, it says infeasible)

And my solution has a better objective value than the current incumbent has.

I also think that my solution is a complete one, that means all variables have solution values
assigned in the value-Array for setSolution.
Do I have to provide values for all variables that exist in my IloEnv or only for those
that are really added to the IloModel?

Do you know anything else that could make setSolution() ignore my solution?
From the output CPLEX gives, there is no indication that CPLEX considers my solution.
It is as if I didn't call setSolution() at all.

Thank you again for helping me!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=Student link=topic=824.msg2469#msg2469 date=1231690339]
So I can rule out two possible causes for my problem.
I definitely know that the solution I want to provide is feasible for my
problem as in the Heuristic Callback I have (as a test) created a copy of my
model to a new Cplex-Object together with the variables fixed at my solution values
and it shows to be feasible and it has the correct objective value for my solution.
(But when I use setBounds() to fix the variables to those solution values and use solve()
inside the Callback to resolve the node, it says infeasible)


Are you resetting the bounds of [i]all[/i] the variables (including the continuous ones, if any)?  You don't want to retain any bounds that CPLEX might have changed during the branching that led to this node.

Also, the documentation warns that you need to be careful not to reset the bounds of a variable that might have been removed by the presolver.  You might try turning presolving off (both at the root node and at later nodes) and see if that changes the behavior of the program.

[quote author=Student link=topic=824.msg2469#msg2469 date=1231690339]
I also think that my solution is a complete one, that means all variables have solution values
assigned in the value-Array for setSolution.
Do I have to provide values for all variables that exist in my IloEnv or only for those
that are really added to the IloModel?


Only those in the model.

[quote author=Student link=topic=824.msg2469#msg2469 date=1231690339]
Do you know anything else that could make setSolution() ignore my solution?


Not off-hand, but of course some subtle coding error cannot be ruled out.

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[hagbard said:]

Hi,

Sorry, I'm not really helping here, but I'm experiencing exactly the same problem.

Actually I find my solution by doing some heuristic approximation, then fixing all binary variables and callining solve().

Now solve returns 'true', getCPLEXStatus() returns 1 (CPX_STAT_OPTIMAL) and getStatus() returns 2 (Optimal). I also can call getObjValue() and recieve a value, that would enhance the incumbet.

But ... returning it to CPLEX (even with setSolution(IloNumVarArray, IloNumArray, obj), in which case CPLEX is ment to just accept the value and not think at all) does not change the value of the incumbent, just as Student described it.


To make things even more absurde: I've built in a parameter to change the frequency of my heuristic. When entering the heuristic, I count the calls and if (nCalls % ratio) != 0, I return immediately.

Now if I use a ratio of 5, I find the first solution somewhere before the 100th BNB-Node, but it is not acceptet. Later on, in node 463 I find a solution, which is accepted. On the other hand, if I set the ratio to 1, I get something like five not accepted solutions before node 200, but nothing is found at all in node 463, which means, I'm getting different data from the node than I did before. This means, the solutions, which were not accepted did have some kind of effect on the branching! - are we encountering a bug?

Maybe my further details on the problem can help you get new ideas - I'll report, if I find a solution!

Chears, John 
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[Student said:]

Hi Paul,

Indeed I had the problem with variables removed by presolve. But neither resetting the bounds
of only the remaining variables nor resetting the bounds of all variables after turning off presolve
(for both root an current node) did help with the call to solve() or setSolution().
(I tried to set the variable bounds back to the original bound values from before optimizing, including
the continuous ones).

A coding error can always occur.
Would it help to post a basic structure of my Callback?


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=Student link=topic=824.msg2532#msg2532 date=1232380264]
Would it help to post a basic structure of my Callback?


It might, but of course no guarantee.

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[Student said:]

Hi Paul,

I have found a possible reason, why setSolution() doesn't work.
It is probably not because of my Callback but because of the logical constraints I use.
Since CPLEX 10 you have the possibility to use socalled "logical constraints" that allow you
to formulate logical implications between expressions.
I use them (in CPLEX 11) to avoid bigM-formulations. For example I use
"IloIfThen(env, IloRange(env, 0, x, 0), IloRange(env, 0, v, 0))" instead of "IloRange(env, v - bigM * x, 0)".

CPLEX transforms these logical constraints into new variables and linear constraints when it extracts them.
But I cannot access these new variables, especially I cannot give them values for setSolution().
So even if the solution I provide has values for all the variables I add myself, it doesn't contain values
for these new variables.
Now when I use the bigM-Formulation instead of logical constraints, CPLEX sometimes accepts
the solution I provide with setSolution()!

So I have at least one way to use my Heuristic-Callback!

Do you know a way to use it together with my logical constraints? Those logical constraints
enable CPLEX to make my MIP much tighter in presolve. Or a these logical constraints generally
not compatible with a Heuristic-Callback?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[gerardo.trevino said:]

I think you already started a negative loop and you are getting away to a solve the problem looking where there is no problem. First of all, you are right, you need to define a single IloNum array with dimension equals to the sum of your 3 original arrays (binary, integer and continuous), but you need to define the upper bounds (I am assuming all your lower bound are 0, if not, just follow the same instructions) for all the elements of the IloNum array as your continuous variables upper bounds, then you need to change just the upper bounds of your integer variables and at last you need to change the upper bounds of your binary variables (to 1). One common mistake is to define initially every upper bound equal to 1 and then change the upper bound to something greater than 1 for the integer and continuous variables, but it does not work because it automatic sets the variable type to binary and even you could change the upper bound of the variable you couldn't change the type of the variable that was already set to binary.

I have another advice, if you are passing to the setSolution the solution value, if better to not do that (it may be omitted). If your result is continuous it is very easy to have a very small difference and your solution then will be invalid.

I hope I could  help you ...

Trevino
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Sorry, no idea whether you can push a solution into the hidden variables.  I'll ping someone inside ILOG to see if they know.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[EdKlotz said:]

Sorry, no idea whether you can push a solution into the hidden variables.  I'll ping someone inside ILOG to see if they know.

The auxiliary variables are not accessible through the object oriented APIs.  They
are available within the heuristic callback within the C API using the CPXgetcallbacknodelp() function.  But, the C API doesn't support methods like
IloIfThen and IloPiecewiselinear, so you need to model those types of constraints
directly, which resolves your original issue. 

If you are using IloIfThen, you do have access to the variables in the constraints
passed to the IloIfThen method.  So, shouldn't your heuristic include some logic to
satisfy the IloIfThen constraints directly?    Also, did you run the solve() command
after setting the values in your heuristic?  Running solve() can help set the unset
variables to their desired values.


Turning presolve off should not be necessary, as CPLEX the heuristic callback method returns all solution values in terms of the original model, not the presolved model.  However, for the moment I suggest you do turn it off, as that at least
simplifies the issue you are trying to resolve.

Finally, you could also model the logical constraints directly.  While that does
potentially create numerical issue due to big M coefficients, it would give you
access to all the variables in the model.  Also, if you can derive reasonable bounds
on the variables and constraints you pass to IloIfThen, you may not have to resort
to using really large values for big M in the model.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[EdKlotz said:]

One other thing; more generally keep in mind that Dual presolve reductions can cause CPLEX to reject a heuristic solution or MIP start.  For example, consider

min x1
st.
x1 >= 0
x1 integer

CPLEX's presolve will recognize that it can push x1 down to its lower bound since no other constraint prevents it from doing so.  This is a dual reduction since CPLEX uses the objective function to make this reduction.  If you provided a MIP start
of x1 = 1, CPLEX would reject it unless you disabled dual reduction.  Even though
that solution is feasible for the original model, it is no longer feasible after preprocessing.  I don't think this is at the core of your current problem, but keep it
in mind when using MIP starts and the heuristic callback in the future.
#CPLEXOptimizers
#DecisionOptimization