Originally posted by: SystemAdmin

Hi everybody,

Think of mathematical model of a practical application in terms of different objects and relationship between them like cars and wheel and engine. When one needs to chose a car, the main thing for he/she would be to chose from among the best formations available and appearance of the car which is composed of different aspects (i.e. different variables in terms of MIPs). With respect to this index one first select the class of problem and then optimizes for the rest (of the variables).

My question is now as following: In a very abstract context, when one need to branch on an object composed of many variables (let say squares, cars etc ) and solve the resulting problem to optimality, what does or how can the user benefit from CPLEX.

Using constraint branching does not seem to be practical as it never worked as I expected.

The modest advanced things I can thing of are ILOSOS1 and ILOSOS2. What if one needs to branch on a configuration modeled by a combination of integer variables.
Any comment is appreciated.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Shahin G wrote:
> Hi everybody,
>
> Think of mathematical model of a practical application in terms of different objects and relationship between them like cars and wheel and engine. When one needs to chose a car, the main thing for he/she would be to chose from among the best formations available and appearance of the car which is composed of different aspects (i.e. different variables in terms of MIPs). With respect to this index one first select the class of problem and then optimizes for the rest (of the variables).
>
> My question is now as following: In a very abstract context, when one need to branch on an object composed of many variables (let say squares, cars etc ) and solve the resulting problem to optimality, what does or how can the user benefit from CPLEX.
>
> Using constraint branching does not seem to be practical as it never worked as I expected.
>
> The modest advanced things I can thing of are ILOSOS1 and ILOSOS2. What if one needs to branch on a configuration modeled by a combination of integer variables.
>
>
> Any comment is appreciated.
I'm not sure I follow your car analogy. But, regarding branching on discrete
entities other than individual variables, CPLEX offers quite a bit:

1. As you mentioned above, you can specify type 1 or type 2 SOSs.
And, with the object oriented APIs, you don't need to bother with
creating type 2 SOSs to formulate piecewise linear functions. You can
instead make use of the IloPiecewiseLinear function and just specify
the slopes and break points.

2. CPLEX also offers indicator variable branching. And, it uses
those indicator variables to offer various logical constraints in the
object oriented APIs (e.g. IloIfThen). But, if you want complete control
of the indicator variables that CPLEX branches on, then you may need the
control of the C API, where you create the individual indicator
constraints and the associated binary variables.
3. If you want to branch on a linear combination of integer
variables, you can do that with the advanced callbacks as well. The
IloCplex::BranchCallbackI::makeBranch routine allows you to branch on
constraints (i.e. hyperplane branching). The left hand constraints
need not even evaluate to integer expressions.

As to whether hyperplane branching is effective, that is another
question. But, when the hyperplane helps identify a thin direction in
the polytope, hyperplane branching tends to work well. That's
essentially what split cuts do. They identify a hyperplane to branch
on, but instead of explicitly branching on it, they do so implicitly,
then extract the information associated with that disjunction into a
cut.

Ed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ed,
thanks for your comments.
I am kinda familiar with the things you mentioned, perhaps not as good as you ;)
The thing is that what I am thinking of is branching on objects more general than SOSs rather than hyperplanes.

Think that I identify part of the model to be suitable for branching then I also introduce the branching rule.

Let say I search for best 3d cube with some object. I need an incumbent to be a 3-d cube but I also know that every branch is a cube which has particular Hamming distance to the current incumbent in terms of the distance between the incidence matrices (I dont know why when I get to this point I always remember local branching of Andrea Lodi).

Now, I need to have a branching system where I declare the object to branch on and also the branching rule. Once the incumbent is detected I can perhaps add some optimality cuts or perhaps some more information to cut off the unnecessary parts and accelerate the convergence.

I dont know if it is understandable enough.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Shahin G wrote:
> Ed,
> thanks for your comments.
> I am kinda familiar with the things you mentioned, perhaps not as good as you ;)
> The thing is that what I am thinking of is branching on objects more general than SOSs rather than hyperplanes.
>
> Think that I identify part of the model to be suitable for branching then I also introduce the branching rule.
>
> Let say I search for best 3d cube with some object. I need an incumbent to be a 3-d cube but I also know that every branch is a cube which has particular Hamming distance to the current incumbent in terms of the distance between the incidence matrices (I dont know why when I get to this point I always remember local branching of Andrea Lodi).
>
> Now, I need to have a branching system where I declare the object to branch on and also the branching rule. Once the incumbent is detected I can perhaps add some optimality cuts or perhaps some more information to cut off the unnecessary parts and accelerate the convergence.
>
> I dont know if it is understandable enough.

Well, CPLEX expects you to provide it with a mathematical programming model.
So, you won't be able to express a 3d cube model explicitly to CPLEX. Now,
if each branch in your cube problem maps to some sort of branch in an associated
MIP, you might be able to make use of CPLEX's branch callback functionality
to implement your model. For example, each branch on one of your objects might
correspond to setting a collection of binary or integer variables to particular
values. But, in such cases, you would need to make sure that the possible branches correspond to all possible values of those integer variables; otherwise
the branch and bound algorithm won't converge. In other words, as an example,
if you have an integer variable x with domain [0,10], you cannot just branch on
x <= 2 and x >= 8. You need other branches that cover the remaining domain
values [3,7].

You might also want to look at some of the modeling objects available in ILOG
CP Optimizer that are not available in CPLEX. Examples include the IloPack and
IloAllDiff constraints. Those or more elaborate constraints that CPLEX doesn't
currently extract. So, they offer you additional discrete modeling objects that
typically translate into multiple integer variables and constraints when you
linearize them in a way that CPLEX can accept.

For example, let's consider the IloAlldiff constraint.

Constructor Summary
public IloAllDiff(const IloEnv env, const IloIntVarArray vars, const char * name=0)

So, in CP-Optimizer, you just input an array of integer variables, and
IloAllDiff constrains them to take on unique values relative to the other
integer variables in the array. CP-Optimizer branches on this constraint;
at any node in the search tree where the variables in the array don't satisfy
the AllDiff constraint, it can alter one or more of the variables to try to
satisfy the constraint. That is a branching step. As long as it branches
in a manner that doesn't miss any possible solutions, the algorithm will terminate
eventually with an optimal solution or proof of infeasibility.

Now, you could implement AllDiff in CPLEX in a couple of ways. First, you could
just provide a linearized representation of the AllDiff constraint. In other
words, for each integer variable, associate some binary variables, then add some
constraints that relate the integer variable to the binaries in a way that each
different set of binary values gives the integer variable a different integral
value within it's domain. Or, you could skip the linearization and create your
own branch callback function that processed the AllDiff directly. You would make
your own branching rules, and you will be responsible to ensure that your
branching rules don't compromise the ability of branch and bound to converge.
Of course, I would only recommend either of these approaches if you had first
tried CP-Optimizer (which now comes as part of CPLEX Optimization Studio, so
doesn't involve any additional cost), and found that you were not getting the
performance you needed from it.

Summarizing, when you have some sort of discrete object that doesn't match any of
the discrete objects (integer variables, SOSs, indicator constraints, IloIfThen,
IloPiecewiseLinear, etc.) that CPLEX explicitly supports, you can either

1) linearize it. But, linearizations like this may lead to weak formulations.
2) create your own branching callback that relates directly to that object.
3) see if CP-Optimizer provides additional discrete objects that help you model
your discrete object. If so, this will save you time from having to formulate
your own branching rules.

Ed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ed, Many thanks for your nice useful comment.
#CPLEXOptimizers
#DecisionOptimization