Operations Research Asked by Farouk Hammami on December 9, 2021

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.

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

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).

Answered by prubin on December 9, 2021

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

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
```

Answered by Alex Fleischer on December 9, 2021

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP