Originally posted by: TRLC
Hello CPLEX forum!
I have often found help in old posts here, but not this time.
I am writing a program in C++ that uses the function IloPiecewiseLinear, but are having troubles. My program compiles and runs, but the optimal solution returned seems to be incorrect. I am verifying the optimal solution by no less than two other models (one without using IloPiecewiseLinear and a homemade Branch-Cut-and-Price), so I think the problem is in my usage of the function IloPiecewiseLinear.
Therefore, I would like some help on understanding how the IloPiecewiseLinear function works.
What I want to model is a left-continuous, non-decreasing, piecewise linear function used in a transportation problem (see the attached file PiecewiseLinearFigure.pdf). As the use is in a transporation problem I will only be considering x-values that are non-negative (x>=0). Maybe not so clear from the figure I want f(0) = 0. Also, note that the function is undefined for x>8 (or infinite in this case).
From the CPLEX documentation there are two ways of passing such a function and I have chosen to define the function by its (x,f(x)) values at the break points (jumps).
What I have done is to define an array with breakpoints and an array with the function values at the break points, with the first break point at zero, like so
breakpoints[0] = 0.0;
functionvals[0] = 0.0; //f(0) = 0
breakpoints[1] = 0.0;
functionvals[1] = 5; //Just an arbitrary example
I then continue to add more segments like
breakpoints[2] = 10;
functionvals[2] = 10;
breakpoints[3] = 10;
functionvals[3] = 14;
And when the last segment with a finite cost has been defined I would add a "dummy" segment with high cost
breakpoints[4] = 15;
functionvals[4] = 26;
breakpoints[5] = 15;
functionvals[5] = 100000000; //Sufficiently high costs
In the end I would then called something like
model.add(costvar[i][j] == IloPiecewiseLinear(flowvar[i][j], 0.0, //slope of the preceding the first breakpoint (which is the segment from -infty to 0)
breakpoints,
functionvals,
1000.0 //Slope of the last segment (which is the undefined part so the slope is sufficiently high)
));
Hence, the example shown here consists of two "real" segments, (0,10] and (10,15].
Some random thoughts on why my costs are incorrect
-
CPLEX probably assumes that the function is right-continuous, such that f(0)=5. I couldn't find it in the manual (and yes, the problem is a minimization problem).
-
If 1) is true, then it should be possible to shift the breakpoints by adding some \epsilon >0. However, this yields some weird behavior by CPLEX, e.g. \epsilon = 0.01 yields z^* = 100, \epsilon = 0.001 yields z^* = 80, \epsilon = 0.0001 yields z^* = 120. I would think it should converges, but maybe this leads to numerical troubles instead.
-
In optimal solution I get several edges with a positive flow equal to some break point, but the cost contribution is 0. The error could possibly be related to to me in some way creating isolated points on the function (which is not supported by CPLEX)? However, I do not receive any errors.
-
If it is of any use, then there always exists an optimal solution which is integer. This yields the possibility of other ways of formulation the problem, but that another story/paper (which has already been done).
I hope this makes sense. At least I tried to make the problem understandable, but it is somewhat technical.
Thanks in advance!
#CPLEXOptimizers#DecisionOptimization