5
$\begingroup$

Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound.

How can we linearize the term $x^2$?

Detailled problem:

Suppose that via a callback we compute a factor namely $A_i \in ]0,1]$. After computing this factor: We need to add the following lazy constraint (using add(modeler,...)):

$x^2_i \le A_i^2 \sum_k \sigma^2_k y_{ki}$; ($x_i \ge 0$, $y_{ki} \in \{0,1\}$ are decision variables and $\sigma_k > 0$ are known parameters).

Adding this lazy constraint results in infeasible status given it is quadratic.

$\endgroup$
2
$\begingroup$

You might want to take a look at two blog posts I wrote earlier this year:

  1. Approximating Nonlinear Functions: Tangents v. Secants
  2. Tangents v. Secants Part II

If you approximate $x^2$ via tangents, all feasible points will satisfy your lazy constraint, but there will be some infeasible points that satisfy it. If you approximate $x^2$ via secants, all points that satisfy the lazy constraint will be feasible, but it will cut off some feasible points. In either case, the more granular the approximation (the more intervals in your piecewise linear function), the closer you get to what you want.

The second post includes some Java code (using CPLEX).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks sir however this does not solve my problem. Concretly: I am solving a quadratic problem using CPLEX and the JAVA API. Suppose that via a callback we compute a factor namely $K \in ]0,1]$. After computing this factor: We need to add the lazy constraint (using add(modeler,...)): $x_{k}^2 \le K \sum_k \sigma_{k}^2 y_{ki}$ ($x_i \ge 0$ and $y_i$ is binary). Adding this lazy constraint results in infeasible status. $\endgroup$ – Farouk Hammami Jul 24 at 12:37
  • $\begingroup$ So CPLEX adds the lazy constraint without any error messages but then concludes the model is infeasible? Do you know a feasible solution that satisfies the new constraint? $\endgroup$ – prubin Jul 25 at 16:38
  • $\begingroup$ CPLEX cannot add these constraints during a callback given they are quadratic thus the solution will be to linearize them. $\endgroup$ – Farouk Hammami Jul 27 at 9:10
1
$\begingroup$

let me adapt the interpolate example from

https://www.linkedin.com/pulse/tips-tricks-opl-cplex-alex-fleischer/

to x*x:

float x[i in 0..sampleSize]=s+(e-s)*i/sampleSize;

int nbSegments=5;

float x2[i in 0..nbSegments]=(s)+(e-s)*i/nbSegments;
float y2[i in 0..nbSegments]=x2[i]*x2[i];  // y=f(x)

float firstSlope=0;
 float lastSlope=0;
 
 tuple breakpoint // y=f(x)
 {
  key float x;
  float y;
 }
 
 sorted { breakpoint } breakpoints={<x2[i],y2[i]> | i in 0..nbSegments};
 
 float slopesBeforeBreakpoint[b in breakpoints]=
 (b.x==first(breakpoints).x)
 ?firstSlope
 :(b.y-prev(breakpoints,b).y)/(b.x-prev(breakpoints,b).x);
 
 pwlFunction f=piecewise(b in breakpoints)
 { slopesBeforeBreakpoint[b]->b.x; lastSlope } (first(breakpoints).x, first(breakpoints).y);
 
 assert forall(b in breakpoints) abs(f(b.x)-b.y)<=0.001;
 
 float maxError=max (i in 0..sampleSize) abs(x[i]*x[i]-f(x[i]));
 float averageError=1/(sampleSize+1)*sum (i in 0..sampleSize) abs(x[i]*x[i]-f(x[i]));

execute
    {

    // turn an OPL array into a python list
    function getPythonListOfArray(_array)
    {

    var quote="\"";
    var nextline="\\\n";


    var res="[";
    for(var i in _array)
    {
    var value=_array[i];

    if (typeof(value)=="string") res+=quote;
    res+=value;
    if (typeof(value)=="string") res+=quote;
    res+=",";
    res+=nextline;
    }
    res+="]";
    return res;
    }

    // Display a function with points with x and y arrays of x and y
    function displayXY(x,y,pythonpath,pythonfile)
    {
    writeln("displayXY ",x," ",y," ",pythonpath," ",pythonfile);

    var python=new IloOplOutputFile(pythonfile);
    python.writeln("import matplotlib.pyplot as plt");
    python.writeln("x = ",getPythonListOfArray(x))
    python.writeln("y = ",getPythonListOfArray(y))
    python.writeln("plt.plot(x, y)");
    python.writeln("plt.xlabel('x - axis')");
    python.writeln("plt.ylabel('y - axis')");
    python.writeln("plt.title('xy graph')");
    python.writeln("plt.show()");
    python.close();
    IloOplExec(pythonpath+" "+ pythonfile,true);        
    }
   

    }
  

    int nbSegments2=10000;

    float x3[i in 0..nbSegments2]=(s)+(e-s)*i/nbSegments2;
    float y3[i in 0..nbSegments2]=x3[i]*x3[i];  // y=f(x)
    float y3pwl[i in 0..nbSegments2]=f(x3[i]);  // y=f(x)

    string pythonpath="C:\\Python36\\python.exe";
    string pythonfile="C:\\temp\\DisplayXY.py";
    execute
    {

    // display x*x function
    displayXY(x3,y3,pythonpath,pythonfile);
    // display pwl approximation
    displayXY(x3,y3pwl,pythonpath,pythonfile);
    } 

and you will see

enter image description here

and later on you may use f as square function:

dvar float xx;
dvar float yy;
subject to
{
  xx==2;
  yy==f(xx);
}    

execute
{
  writeln("yy=",yy);
}

gives

yy=4
| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Can you write your approach out algebraically in addition to your code? $\endgroup$ – LarrySnyder610 Jul 23 at 13:45
  • $\begingroup$ Thank you for your reply however it does not help. The problem i am solving using CPLEX and Java comes from the fact i need to add several lazy constraints and these contain a quadratic term however Lazy Constraints must be linear otherwise the problem is considered infeasible. The form of the lazy constraint that i need to add during the solve procedure is $x^2 \le \sum y_k$ $\endgroup$ – Farouk Hammami Jul 23 at 14:12
  • $\begingroup$ Ok what I offered is in OPL but you could do the same with java concert API or even call OPL from java. $\endgroup$ – Alex Fleischer Jul 23 at 14:22
  • 1
    $\begingroup$ As suggested by @LarrySnyder610, would you share the solution algebraically? I might help many researchers. Thanks. $\endgroup$ – Farouk Hammami Jul 23 at 14:28
  • $\begingroup$ y=f(x) where f is x->x*x. Since f is not linear we can replace f by a piecewise linear function that is not too far from f. That's all.You may use Transport.java as an example for piecewise linear cost function in java cplex $\endgroup$ – Alex Fleischer Jul 23 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.