Handling of piecewise linear constraint using gurobi 6.0

[dips]

Hi All,

I am using gurobi 5.5 version for solving my Piecewise linear approximation problems in which both objective function and constraints are piecewise linear function. In GUROBI 6.0 version there is in-built piecewise linear objective support . In the following manual example of that it is shown that only Objective function can be made peicewise linear . Would anybody explain how to use this in-built piecewise support for piecewise linear objectives? 

The example is,

piecewise.m

% Copyright 2014, Gurobi Optimization, Inc.

% This example considers the following separable, convex problem:
%
%   minimize    f(x) - y + g(z)
%   subject to  x + 2 y + 3 z <= 4
%               x +   y       >= 1
%               x,    y,    z <= 1
%
% where f(u) = exp(-u) and g(u) = 2 u^2 - 4 u, for all real u. It
% formulates and solves a simpler LP model by approximating f and
% g with piecewise-linear functions. Then it transforms the model
% into a MIP by negating the approximation for f, which corresponds
% to a non-convex piecewise-linear function, and solves it again.

names = {'x'; 'y'; 'z'};

try
    clear model;
    model.A = sparse([1 2 3; 1 1 0]);
    model.obj = [0; -1; 0];
    model.rhs = [4; 1];
    model.sense = '<>';
    model.vtype = 'C';
    model.lb = [0; 0; 0];
    model.ub = [1; 1; 1];
    model.varnames = names;

    % Compute f and g on 101 points in [0,1]
    u = linspace(0.0, 1.0, 101);
    f = exp(-u);
    g = 2*u.^2 - 4*u;

    % Set piecewise linear objective f(x)
    model.pwlobj(1).var = 1;
    model.pwlobj(1).x   = u;
    model.pwlobj(1).y   = f;

    % Set piecewise linear objective g(z)
    model.pwlobj(2).var   = 3;
    model.pwlobj(2).x     = u;
    model.pwlobj(2).y     = g;

    % Optimize model as LP
    result = gurobi(model);

    disp(result);

    for v=1:length(names)
        fprintf('%s %d\n', names{v}, result.x(v));
    end

    fprintf('Obj: %e\n', result.objval);

Thanks and regards

[Jakob Sch.]

Hi dips,

As you can see in the example you have to specify the variable that is affected by the function and the points (value and function(value)) that specify the piecewise linear function. From the manual: http://www.gurobi.com/documentation/6.0/reference-manual/matlab_gurobi

pwlobj (optional)

The piecewise-linear objective functions. A struct array. When present, each element in the array defines a piecewise-linear objective function of a single variable. The index of the variable whose objective function is being defined is stored in model.pwlobj.var. The x values for the points that define the piecewise-linear function are stored in
model.pwlobj.x. The values in the vector must be in non-decreasing order. The y values for the points that define the piecewise-linear function are stored in model.pwlobj.y.

best regards,
Jakob

[szx]

Hello,

Will there be piecewise linear constraint support in future versions?

Moreover, will there be piecewise linear expressions which are able to occur in ordinary linear expressions? (e.g. pwl(x) + 3*y)

Thanks!

[Tobias Achterberg]

Piece-wise linear constraints are definitely on our list of things to consider,
but it is not clear when or whether we will actually include them in the product.

Best regards,

Tobias

[Srikrishnan Lakshmanan]

Hi Tobias

1.When a piece-wise linear objective is specified , does it mean that the function can only take discrete values (specified in the double[] x , y combinations) . Or can it take intermediate values considering the y to be extrapolated linearly between its surroundings.

2. Following from question (1) above,when piece wise linear objective is specified , can one of the x,y pairs be an open limit such as (-3.0,0]. 

3. From the solutions in the examples supplied , the solution for a pwl problem appears to be restricted to the values supplied , and not any intermediate values in between two specified points. 

If (3) is true, this would limit the use of the pwl function tremendously . 

[Tobias Achterberg]

1. The variable can take any value in its domain. If it is a continuous variable, then it
can of course also take fractional values. The piece-wise linear function then specifies
the variable's contribution to the objective function, which is given by a convex
combination of two adjacent break-points.

2. Yes, you can specify discontinuous piece-wise linear functions. For example, the points
{(0,0), (10,0), (10,1), (20,1)} define a step function that is 0 in [0,10) and 1 in
(10,20]. The value at the discontinuous point 10 will be the better of the two options.
Thus, if you are minimizing, the objective value at point 10 will be 0.

3. See above.

Please see http://www.gurobi.com/documentation/8.0/refman/py_model_setpwlobj.html for
further details.


Best regards,

Tobias