Originally posted by: rourou

IloLexicographic(IloEnv env, IloIntExprArray x, IloIntExprArray y, const char *=0)

for example there are two arrays a(1,2,3) and b(2,1,3),how to use IloLexicographic to returns a constraint which maintains two arrays to be lexicographically ordered?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Your question may reach a knowledgeable audience if you also repost it to the CP Optimizer forum at http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2066.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Actually, I was curious about this myself. IloLexicographic apparently exists in the C++ API to CPLEX but not the Java API. Does it enforce lexical ordering by adding a bunch of indicator-type constraints (with implicit big-Ms floating around)? Or does it enforce lexical ordering by directly modifying the branching process? Or by turning into a stack of goals? Inquiring minds want to know!

/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: EdKlotz

> Paul Rubin wrote:
> Actually, I was curious about this myself. IloLexicographic apparently exists
> in the C++ API to CPLEX but not the Java API. Does it enforce lexical ordering > by adding a bunch of indicator-type constraints (with implicit big-Ms floating
> around)? Or does it enforce lexical ordering by directly modifying the
> branching process? Or by turning into a stack of goals? Inquiring minds want
> to know!
>
> /Paul
>

IloCplex does not extract constraints created via IloLexicographic; only CP
Optimizer does.

In the C++ API reference manual, the description of Logical Constraints states:

In fact, the class IloCplex can extract logical constraints as well as some logical expressions. The logical constraints that IloCplex can extract are these:

IloAnd which can also be represented by the overloaded operator &&
IloOr which can also be represented by the overloaded operator ||;
IloDiff which can also be represented by the overloaded operator !=;
IloNot, negation, which can also be represented by the overloaded operator !;
IloIfThen
== (that is, the equivalence relation)
!= (that is, the exclusive-or relation)
And the list of classes IloCplex can extract are:

*IloNumVar numeric variables
IloSemiContVar semi-continuous or semi-integer variables
IloObjective at most one objective function with linear, piecewise linear, or quadratic expressions
IloRange range constraints with linear or piecewise linear expressions
IloConstraint ranged constraints of the form expr1relationexpr, where expr1 indicates a linear, logical, or quadratic expression and the relation less than or equal to or the relation greater than or equal to; constraints can be combined by logical operators
IloConversion variable type conversions
IloModel submodels
IloSOS1 special ordered sets of type 1
IloSOS2 special ordered sets of type 2
IloAnd constraint clauses*
While IloCplex doesn't extract IloLexicographic directly, I think you can
use the logical constraints it does extract to express the lexicographic
constraints fairly easily. For example, if x and y are the IloIntExprs you want to constraint
to order lexicographically, create an IloBoolVarArray z of the same length as
x and y. Then add the constraints

y[i] <= x[i] i = 1,...,n
IloIfThen(env, y[i] >= x[i], z[i] <= 0)
IloIfThen(env, y[i] + 1 <= x[i], z[i] >= 1)

The two IloIfThen constraints specify that when y[i] = x[i], z[i] = 0
and when y[i] < x[i], z[i] = 1. The latter IloIfThen constraint accomplishes
this because y[i] and x[i] are integer expressions, so they must differ by at
least one when separated by a strict inequality. So, now we just need
to make sure that the elements of z[i] after the first one that takes on a value
of 1 are also all 1:

zi] <= z{i+1 i = 1,...,n-1
I think that should do it. That reduces Paul's question about how IloCplex
does the linearization to how IloCplex linearizes IloIfThen. Currently that
is indeed based on indicator variables (as can be seen if you export an LP file
from a model containing IloIfThen constraints). However, keep in mind that
this is an undocumented, under the hood feature of CPLEX, so it could change in
the future if we found a better way to perform the linearization.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ed,

Thanks for the explanation. One correction, though:

> y[i] <= x[i] i = 1,...,n

This would be overly restrictive. What you need is something like IloIfThen(env, z[i] == 0, y[i] <= x[i]). (Although I'm not guaranteeing that, coupled with the rest of your answer, that is correct.) I've already got something like this coded in one application. I was hoping for a "silver bullet", but it looks like IloLexicographic won't simplify things any for me in a CPLEX (as opposed to CP) application.

Thanks.

/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: EdKlotz

> Paul Rubin wrote:
> Ed,
>
> Thanks for the explanation. One correction, though:
>
> > y[i] <= x[i] i = 1,...,n
>
> This would be overly restrictive. What you need is something like
> IloIfThen(env, z[i] == 0, y[i] <= x[i]). (Although I'm not guaranteeing that,
> coupled with the rest of your answer, that is correct.) I've already got
> something like this coded in one application. I was hoping for a "silver
> bullet", but it looks like IloLexicographic won't simplify things any for me in > a CPLEX (as opposed to CP) application.

My apologies. The constraints I described model the condition that there exists i < size(x) such that for all j < i, x[j] = y[j], and x[k] > y[k] for all k >=i.
But, that is not the condition the IloLexicographic models.

So, let me try again. If you want to model IloLexicographic (env, x, y), you
could do it with the following constraints. Keep in mind that this relies on
the fact that x and y are IloIntExprs; this does not cover the case of continuous
linear expressions, where you need to deal with tolerances to handle the strict
inequalities.

IloBoolVarArray z(env, x.getSize());
IloBoolVarArray w(env, x.getSize());

n-1
sum z[i] = 1
i=0

IloIfThen (z[i] >= 1, x[i] + 1 <= y[i]) // identifies the index i which we must have x[i] < y[i]
i
w[i] = sum z[j] // w[k] = 0 for k < i, 1 otherwise
j=0

IloIfThen (w[i] <= 0, x[i] == y[i]) // forces x[k] = y[k] for k < i.
// For k > i, w[k] = 1,
// which doesn't impose any restriction
// on the relation between
// between x[k] and w[k]
#CPLEXOptimizers
#DecisionOptimization