How do I express optimization variable as ones and zeros in constraints?

Hi!

I struggle with an optimization problem with four optimization variables x1 to x4, all with size 24x1. I have formulated the problem as an integer linear program, i.e. all variables are positive integers only, between 0 and 5.

My problem is the following: I would like to create a constraint which results in that maximum one variable can be nonzero in every row. E.g, if x1(1,1) is non-zero, then x2(1,1), x3(1,1) and x4(1,1) should be zero.

I tried to solve this using Matlab functions "spones" in combination with "full", ending up with the following constraint:

full(spones(x1)) + full(spones(x2)) + full(spones(x3)) + full(spones(x4)) <= 1

, in hope that the solver then would consider ones and zeros only and limit the sum to one. Although, when doing, this I get an error from "spones" saying that the "find" function is used with wrong type or with incorrect number of inputs.

I could of course change optimization method, and implement new variables which are between 0 and 1. But I would like to investigate if there are any smart tricks to solve it without changing method.

Please let me know your thoughts on this!!

BR

Johannes

[Torsten]

You said you want to have x1,...,x4 to be integers between 0 and 5.

Now you want to constrain them as

x1(1:24) + x2(1:24) + x3(1:24) + x4(1:24) <= ones(24,1).

So x1,...,x4 become integers between 0 and 1 instead of 0 and 5.

Is it this what you want ?

[Johannes Hjalmarsson]

Not exactly, sorry if I was not specific enough!

I still want to keep my original variables x1 to x4 between 0 and 5, but I would like to add a constraint which prevents that not more than one variable is non-zero in every row. Trying to figure out if there are any smart ways of dealing with this without adding more variables... Using ones and zeros was just one of my suggestions, but I'm open for all solutions!

[Torsten]

Using ones and zeros was just one of my suggestions

Yes, but it restricts the values in x1,...,x4 to 0 or 1 (which - as far as I understood now) is not what you want.

I think you will have to introduce the contraints

x1(i) + x2(i) + x3(i) + x4(i) = max(x1(i),x2(i),x3(i),x4(i))

which means that you will have to introduce new binary variables to express the maximum expression.

[Johannes Hjalmarsson]

Yes, you're right. I find it tricky to work around this issue without compromising the range of possible values of x1 to x4, or without introducing new variables.

[Torsten]

Won't work without introducing new (binary) variables.

Here is one way to handle the max(...) expression:

https://or.stackexchange.com/questions/6035/linearizing-a-max-function-in-the-constraint-not-working

Answer 1

[Matt J]

You would need to introduce additional binary variables Z:

X=optimvar('X',24,4,'Lower',0,'Upper',5,'type','integer');  %original variables
Z=optimvar('Z',24,4,'Lower',0,'Upper',1,'type','integer');  %additional variables

Con.Zlow=Z>=X/5; %X>0 implies Z=1
Con.Zhigh=Z<=X;  %X=0 implies Z=0

Con.Zrows=sum(Z,2)<=1; %Only 1 element/row of Z (and therefore of X) can be non-zero


prob=optimproblem('Constraints',Con)

prob = 
  OptimizationProblem with properties:

       Description: ''
    ObjectiveSense: 'minimize'
         Variables: [1×1 struct] containing 2 OptimizationVariables
         Objective: [0×0 OptimizationExpression]
       Constraints: [1×1 struct] containing 3 OptimizationConstraints

  See problem formulation with show.

[Johannes Hjalmarsson]

Yes, thank you for the fast answer and for verifying this!! I have tried to implemented a similar solution to this and it works, but it requires me to drop my linear programming approach since I get nonlinear terms with X*Z in the objective function.

[Matt J]

Are you saying you're having the same problem with my solution? I don't see why. X.*Z=X under the constraint formulation I've proposed, so Z never need appear in the objective function.

If my solution does work for you, kindly Accept-click it.

[Johannes Hjalmarsson]

Your proposed solution worked fine, just implemented it in my code and I did not have to change method either!

It was smart to introduce variables which are not included in the objective function, I did not think of that before. Thank you for the input and the help with solving this issue!

BR

Johannes