Unable to do a piecewise linear optimization of two variables

[Parth Nagarkar]

Hello,

My question is similar to this post (https://groups.google.com/forum/#!topic/gurobi/YUWqUfk3PSc). The author's second question was not answered. So I am asking again.

I am trying to solve the following integer linear function:

minimize:  |3x+4y - 175|

s.t.  x+y = 50

I understand, from previous posts, that the absolute value is a piecewise linear function. The examples that I have been reading show the solution when there is an absolute value taken of x or y individually (not the function as a whole). 

This is what I have come up with (by trying to modify the code given at: http://www.gurobi.com/documentation/7.0/examples/piecewise_cpp_cpp.html#subsubsection:piecewise_c++.cpp):

My thought process was: declare z = f(x, y) = |3x + 4y - 175|, and do the piecewise linear optimization. Inside the first for loop, I don't know if it was right of me to write the following: (ptz[i] = f(ptu[i], ptu[i]);). I am getting the results as x=50 and y=-0, when the result should have been x=y=25. Could someone please point out to what I am doing wrong? Thanks! 

double f(double u, double v) { return abs(3*u + 4*v - 175); }

int

main(int   argc,

     char *argv[])

{

  double *ptu = NULL;

  double *ptz = NULL;

  try {

    GRBEnv env = GRBEnv();

    GRBModel model = GRBModel(env);

    // Create variables

    double lb = 0, ub = 50;

    GRBVar x = model.addVar(lb, ub, 0.0, GRB_INTEGER, "x");

    GRBVar y = model.addVar(lb, ub, 0.0, GRB_INTEGER, "y");

    GRBVar z = model.addVar(0, 25, 0.0, GRB_CONTINUOUS, "y");

    // Add piecewise-linear objective functions

    int npts = 101;

    ptu = new double[npts];

    ptz = new double[npts];

    for (int i = 0; i < npts; i++) {

      ptu[i] = lb + (ub - lb) * i / (npts - 1);

      ptz[i] = f(ptu[i], ptu[i]);

    }

    model.setPWLObj(z, npts, ptu, ptz);

    // Add constraint

    model.addConstr(x + y == 50, "c0");

    // Optimize model as an LP

    model.optimize();

    // Negate piecewise-linear objective function for x

    for (int i = 0; i < npts; i++) {

      ptz[i] = -ptz[i];

    }

    model.setPWLObj(z, npts, ptu, ptz);

    // Optimize model as a MIP

    model.optimize();

    cout << "IsMIP: " << model.get(GRB_IntAttr_IsMIP) << endl;

    cout << x.get(GRB_StringAttr_VarName) << " "

         << x.get(GRB_DoubleAttr_X) << endl;

    cout << y.get(GRB_StringAttr_VarName) << " "

         << y.get(GRB_DoubleAttr_X) << endl;

    cout << "Obj: " << model.get(GRB_DoubleAttr_ObjVal) << endl;

  } catch(GRBException e) {

    cout << "Error code = " << e.getErrorCode() << endl;

    cout << e.getMessage() << endl;

  } catch(...) {

    cout << "Exception during optimization" << endl;

  }

  delete[] ptu;

  delete[] ptz;

  return 0;

}

[Daniel Espinoza]

Dear Parth,

Some comments with your code:

1.- You are using the variable name "y" twice (this may create problems when writing the problem or querying variables by name

2.- It seems that the upper bound of z is wrong

3.- piece-wise functions should only depend on one variable, not two, one way to get around it is to realize that given x+y = 50, then |3x + 4y - 175| = |3x + 4(50-x) - 175| = |25 - x| and set a PWL objective for x

4.- In your case (I think) you don't need to complement the objective, as after the first call you already had solved (if well formulated) your problem.

5.- There is an alternative to handle min | 3x + 4 y -175|, and this involves adding an extra variable z as follows:

min z

s.t. x + y = 50

      3x + 4y - 175 <= z

     -3x - 4y + 175 <= z

      x, y >= 0

Note that z >= |3x + 4y - 175|, but at optimality z will be equal to |3x+4y-175|

Best

Daniel

[Michael Winkler]

One additional comment, since our 7.0 release you can use new supported types of constraints, the so-called general constraints, e.g., an ABS constraint. In your case you would need an additional artificial variable z with the linking constraint z = 3x + 4y - 175, then the ABS constraint z' = ABS(z). In LP format it looks like:

Minimize
 z'
Subject To

 x + y = 50

 z - 3 x - 4 y = -175
Bounds
GENCONS
 z' = ABS ( z )
End

See also https://www.gurobi.com/documentation/7.0/refman/constraints.html#subsubsection:GeneralConstraints

Best, Michael

[Parth Nagarkar]

Thank you Daniel! Your solution worked. I was fixated on solving it as shown in the above link, but thank you for your elegant and simple solution.

[Daniel Espinoza]

Glad to hear that ;-)