2

I want to write an optimization model which selects the lesser of the two tasks, depending upon some constraint. 

minimize obj: (doT1 * T1) + (doT2*T2) + (additional variables)

Now, T1 and T2 represent duration of tasks, and doT1 represents flag to do these tasks. I want this optimization to select only one of them if needed.

When I put the constraint 

s.t. c15: 0<= doT1 <= 1;
s.t. c15: 0<= doT2 <= 1;

I get an error message which in glpsol which says that multiplication of linear forms not allowed.

Is it possible to express the OR condition in linear programming?

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
Asif Shiraz
  • 864
  • 1
  • 12
  • 27

1 Answers1

1

gplsol is most likely complaining about the product of variables doT1 * T1 and doT2 * T2.

I'm assuming that doT1 and doT2 are binary variables, and T1 and T2 are continuous variables (representing the duration of tasks). (Note that this means you will have to use a mixed integer programming solver rather than a pure linear programming solver. You might also want to try using a powerful MIP solver like Gurobi).

You can construct your model by rewriting your constraints and objective as

  minimize  T1 + T2 + (additional variables)

   st        T1 <= UT1*doT1
             T2 <= UT2*doT2
             doT1 + doT2 <= 1
             doT1, doT2 binary
             (plus any additional constraints)

where UT1 is an upper bound on the duration of task T1 and UT2 is an upper bound on the duration of task T2. If doT1 = 0 then T1 <= 0, so the task will not be completed. If doT1 = 1, then T1 <= UT1, meaning that task T1 is allowed to take some duration. The same holds for T2.

The OR condition is expressed by the constraint doT1 + doT2 <= 1. This constraint means that doT1 and doT2 cannot both be 1. That is only one job can be selected. Note that the <= constraint also allows you to not perform either task. If at least one task must be completed, you want to use the constraint doT1 + doT2 == 1.

codehippo
  • 1,379
  • 1
  • 8
  • 19