Weird result of CPLEX "cplexmilp" function in MATLAB

Question

According to my previous question, I want to optimize an objective function using binary integer linear programming (all of variables are binary) as follows:

Minimize f = (c1*x1) + (c2*x2) + MAX((c3*x3),(c4*x4)) + (c5*x5)
Subject to: some equality and inequality constraints

For MAX operator, I used auxiliary variable x6 and added x6>=(c3*x3) and x6>=(c4*x4) constraints to the problem so the problem turn into:

Minimize f = (c1*x1) + (c2*x2) + x6 + (c5*x5),  with added constraints.

I used CPLEX API for MATLAB to optimize the objective function.
Because all of variables are binary except one ((x6) which is continuous) and coefficients have double values, the problem turn into mixed integer linear programming so I used cplexmilp function with this configuration:

• Variable types: ctype='BBBBBC' ( B:Binary, C:Continuous)
• Lower Bounds: lb=[0 0 0 0 0 0]
• Upper Bounds: ub=[0 0 0 0 0 inf]
• Function Call: [fval] = cplexmilp(f, Aineq, bineq, Aeq, beq,[],[],[],lb,ub,ctype)

but sometimes in the results I see x3 and x4 have continuous values(between 0 and 1) and x3+x4=1. So my questions are:

1. Can any one tell me what's wrong with x3 and x4?
2. Is there a solution for not using auxiliary variable and solving this optimization problem with cplexbilp ?

Thanks in advance

[UPDATE]:
One parts of my code had logical errors which I fixed them, now in all cases which x3 and x4 are not binary we have x3*(1-x3)< 10^(-5), x4*(1-x4)< 10^(-5) and x3+x4=1, so @David Nehme were right (according to his useful comment), but my second question still remains here!

Answer 1

David's solution shows you why your formulation has become linearized but non-binary. You could also try printing out the problem in LP or MPS format to see all the resulting constraints.

You asked about a formulation that continues to be purely binary. Here's one way to do that:

Transforming this to a purely binary formulation

Here's a way to keep the problem with Max() also binary. It involves additional aux. variables, but it is relatively straight-forward once you apply the standard if-then IP tricks.

First, let's list out the four possible cases in a simple table, and see what values the max() term can take. These cases are mutually exclusive.

  x3 | x4 | max (c3.x4, c4.x3)
 -------------------------------
  0   | 0 | 0
  1   | 0 | c3
  0   | 1 | c4
  1   | 1 | max(c3, c4) - a constant

Now, let C34 be the max(c3, c4). Note that C34 is a number, not a variable in the problem. We need this for the new Objective function.

Introducing new binary variables

For each of the four cases above, let's introduce an auxiliary BINARY variable. For clarity, call them y0, y3, y4, y34.

Only one of the cases in the table above can hold, so we add:

y0 + y3 + y4 + y34 = 1 
yi are BINARY

Now, all that remains is to add linking constraints that ensure:

 If x3=0 AND x4=0 then y0=1
 If x3=1 AND x4=0 then y3=1
 If x3=0 AND x4=1 then y4=1
 If x3=1 AND x4=1 then y34=1

We can ensure that by adding a pair of linear constraints for each of the conditions above.

   2 y0 <= (1- x3) + (1 -x4)
  (1-x3) + (1-x4) <= y0 + 1

   2 y3 <= x3 + (1-x4)
  x3+(1-x4) <= y3 + 1

   2 y4 <= x4 + (1-x3)
  x4+(1-x3) <= y4 + 1

   2 y34 <= x3 + x4
  x3+x4 <= y34 + 1

The new objective function now becomes:

   Minimize f = (c1*x1) + (c2*x2) + (c5*x5) + 0*Y0 + C3*Y3 + C4*Y4 + C34*Y34

Notice that we don't have the Max() term anymore in the objective function. And all x and y variables are binary. All your original constraints plus the new ones above (8+1 = 9 of them) should be included. Once you do that, you can use cplexbilp because it is a pure BILP problem.

Hope that helps.

Answer 2

In your case, the auxiliary variable x6 is needed because the "MAX" function is not linear (it has a discontinuous gradient where c3*x3 == c4*x4). By adding the additional variable and constraints you are creating a linear version of the problem with a solution that is equivalent to your original nonlinear problem. The trade-off is that if c3 or c4 have a value other than 0 or 1, then your problem is not a pure binary problem. That is a very good trade-off, especially if you are using a good MIP solver.