Originally posted by: SystemAdmin

Hi,

I am using CPLEX 12.4 with C to solve a special Mixed-Integer Quadratic Programming (MIQP)
with the form: min {q(x): x\in X}, where X is a mixed-integer set and q(x) is a convex quadratic function.

The special structure of the problem allows me to dynamically generate special cuts at each node of the
branch-and-cut process, but the cut (valid inequality) expression has an additional variable v and the
the objective function q'(x,v) of the subproblem at each node is different from q(x), it is a relaxation:
q'(x,v)<=q(x). If I feed CPLEX with q'(x,v) as an objective function, then CPLEX only gives me a
feasible solution to the original problem, not the optimal one, because the objective function q(x)
has been changed to q'(x,v).

In order to get the correct optimal solution to the original problem, I need to change
the upper bound from q'(x,v) to q(x) whenever CPLEX finds a feasible solution x.
My question: Is it possible to do this using cutcallback (or incumbent callback, branching callback),
or implement this using other tricks?

Thanks a lot!

Xiaojing Zheng
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I'm struggling to understand what it is you are trying to do. It sounds as though you are solving a problem (P) containing x (but not v), using a cut callback to generate cuts at each node of the tree for (P) by working with a relaxation (P') containing both x and v. Why you feel the need to introduce the objective of (P') into (P) (except you can't), or fiddle with the bound at a node (only when an incumbent for (P) is found?) is what I don't get. If the issue is that the cuts you generate contain v, perhaps you can add v to (P), including it in a vacuous constraint (but not in the objective). My guess is you will need to turn off presolving to avoid having CPLEX eliminate v, but perhaps not.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi,

Many thanks for your information.

In fact, what I do is as following.

During the branch and cut, everytime cplex get an incumbent, I want to use my upper bound, instead of using the upper bound defined by cplex. My upper bound is better than the upper bound defined by cplex. And my upper bound is also updating when a new incumbent is achieved.

I want to know is that possible to achieve this and how?

Best wishes,

xjz
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Dear all,

Since I come across a new problem. Thus I restate the problem here.

My problem is to minimize a MIQP: min f(x) s.t. x\in X.

As we know, during the branch and bound process, if we obtain a lower bound whose value is larger than the existing upper bound, this branch will be stopped. Cplex's main idea of branch and bound must follow this.

Now my aim is to find another optimal solution to minimize other objective function h(x) with same feasible set. In general, for any x\in X, f(x)<= h(x).

Now suppose that I can not ask the cplex to solve problem min h(x) s.t. x\in X. I can only ask cplex to solve the cplex solve min f(x) s.t. x\in X. Obviously, the optimal solution cplex for minmize f(x) is not what I want.

Thus, I want to change the upper bound of cplex for minimize f(x) during the branch and bound. Specifically, when an incumbent y is found, cplex will update upper bound as f(y) if f(y) is smaller than existing upper bound. What I want is can we update upper bound as h(y) if h(y) is smaller than existing upper bound? Note that h(y)>= f(y), maybe CPXaddmipstarts can not be used to achieved this.

If I cannot, when the lower bound is larger than upper bound, can I use the branch callback to ask the cplex to continue branching rather than stopping?

I am looking forward for your replying.

Many thanks!

xjz
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you can do (but this is not recommended at all) is to use a heuristic callback, inject a heuristic solution and lie to CPLEX about the objective function value of this heuristic solution. Every API has a way to inject a solution and make CPLEX accept whatever objective function value you provide. This way you can trick CPLEX into believing that it has found a better solution. As I said, this is not recommended and also error prone.
What you could do instead is to keep track of your upper bound yourself. Then hook into the appropriate callbacks to do the following:
1. As soon as the global lower bound exceeds your upper bound stop the optimization (you know that you have found the optimal solution).
2. If you encounter a node for which the relaxation exceeds your upper bound then prune this node.

I did not understand your goal completely but I feel uncomfortable with the idea of "solving for objective function f() but submitting a different objective function h() to CPLEX". I don't really understand why you cannot submit f to CPLEX directly.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi,
Many thanks for your information. I want to explain why I can not minimize h(x) directly via cplex and what I want to do .

The original problem I want to solve is a mixed-integer quadratic program:
(P) min q(z)+\sum^n_{i＝1} d_ix_i^2
s.t. (x,z)\in Q
0<=x_i<=y_i, i=1,...,n
y_i\in{0,1}, i=1,...,n
where q(z) is a convex quadratic function, d_i>0 for each i, Q is a polyhedron in (x,z) space,.

I know this problem can be directly handled by CPLEX. But I am trying to implement
a new method in which a class of so-called perspective cuts are generated and added
dynamically at each nodes of the branch-and-bound tree. This kind of perspective
cuts are based on a reformulation of the original problem. We have known that the problem (P)
is equivalent to the following semi-infinite MIQP:
(P1) min q(z)+\sum^n_{i=1} v_i
s.t. v_i>=C(x_i,y_i; x'_i), i=1,...,n, x'_i\in 0,1,
(x,z)\in Q
0<=x_i<=y_i, i=1,...,n
y_i\in{0,1}, i=1,...,n
where v_i>=C(x_i,y_i; x'_i) is a linear valid inequality (perspective cut) at point x_i'. The above
problem cannot be solved directly because there are infinite number (uncountable) of cuts constraints.
Nevertheless, it is possible to use an iterative approximation technique whereby a small subset of the cuts
are used to construct a QP relaxation (after relaxing y_i\in{0,1} to y_i\in 0,1).

We may use cutcallback to generate the cuts dynamically at each node of the branch-and-bound search
tree and the QP relaxation subproblem gives a lower bound to the original problem (P). If we input
the objective function of (P1) to CPLEX and solve the QP relaxation (after adding cuts) at each node,
then CPLEX does not give us an optimal solution of (P) when it terminates because the upper bound
calculated by the objective function of (P1) is NOT necessarily an upper bound of the optimal value of (P).
This is way we need to insert a new upper bound whenever a feasible solution (where y_i is binary) is found, i.e.,
the upper bound should be computed by the objective function of (P) instead of (P1).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi, many thanks for your information.
However, when I try to apply your suggestion as following:
>I did not understand your goal completely but I feel uncomfortable with the idea of "solving for >objective function f() but submitting a different objective function h() to CPLEX". I don't really >understand why you cannot submit f to CPLEX directly.
In fact, I am trying "solving for objective function h() but submitting a different objective function f() to CPLEX". Thus, my upper bound is larger than cplex's upper bound.

>What you could do instead is to keep track of your upper bound yourself. Then hook into the >appropriate callbacks to do the following:
>1. As soon as the global lower bound exceeds your upper bound stop the optimization (you know that >you have found the optimal solution).
> 2. If you encounter a node for which the relaxation exceeds your upper bound then prune this node.

Yes, it is the case. However, what I want to do additionally is :
1. As soon as the global lower bound exceeds cplex's upper bound, but not exceeds my upper bound, I do no want stop the optimization. In fact, in this case, cplex will stop automatically, what can I do to continue the optimization.
2. If a node for which the relaxation exceeds cplex's upper bound, but less than my upper bound, I want to continue this node, rather than prune this node.

Can you kindly give some suggestions to do the above? Many thanks.

xjz
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> However, when I try to apply your suggestion as following:
> >I did not understand your goal completely but I feel uncomfortable with the idea of "solving for >objective function f() but submitting a different objective function h() to CPLEX". I don't really >understand why you cannot submit f to CPLEX directly.
> In fact, I am trying "solving for objective function h() but submitting a different objective function f() to CPLEX". Thus, my upper bound is larger than cplex's upper bound.
>
As far as I understood you have two different models: P and P1. They are equivalent but P1 has a very large number of constraints/cuts. So you cannot formulate P1 explicitly but instead want to handle the large number of constraints via separation.
I still don't get why you do not submit P1 to CPLEX. Is it just because a feasible solution to P1 may not be a feasible solution to P? Can't you find a way to transform a solution for P1 to a solution for P so that you can work with P1 all the time and only need to transform the solution as the final step?
> >What you could do instead is to keep track of your upper bound yourself. Then hook into the >appropriate callbacks to do the following:
> >1. As soon as the global lower bound exceeds your upper bound stop the optimization (you know that >you have found the optimal solution).
> > 2. If you encounter a node for which the relaxation exceeds your upper bound then prune this node.
>
> Yes, it is the case. However, what I want to do additionally is :
> 1. As soon as the global lower bound exceeds cplex's upper bound, but not exceeds my upper bound, I do no want stop the optimization. In fact, in this case, cplex will stop automatically, what can I do to continue the optimization.
> 2. If a node for which the relaxation exceeds cplex's upper bound, but less than my upper bound, I want to continue this node, rather than prune this node.
>
So you want tell CPLEX to use a larger bound than the bound given by the best feasible solution? That is not possible. What you can do is:
1. Implement an incumbent callback that just rejects all integer feasible solutions. This way CPLEX will never see a feasible solution and will always work with an infinite upper bound.
2. Keep track of your own upper bound and do node pruning based on this upper bound in the branch callback.
3. You also need to keep track of feasible solutions yourself since CPLEX can no longer do that for you (due to 1).
Note that the incumbent callback may be called for solutions found by heuristics and for nodes that have an integral solution of the node relaxation. If you reject an integral node then you must provide your own branching for that node. Otherwise the solution process may go haywire.
#CPLEXOptimizers
#DecisionOptimization