I am trying to build a MILP.
I need to set the number of linear constraints in the model as a decision variable.
For example:
max 8* x1 + 6 * x2 - x3
s.t.
constraint 1 : x1 + x2 <= 29
constraint 2 : x1 - x2 <= 5
constraint 3 : x2 + x3 <= 56
0 <= x1 <= 50, 0 <= x2 <= 30, 0 <= x3 <= 70
x1, x2 are int
I would like to make the all three constraints as candidates such that
- the objective maximized.
At least one constraint must be active
"Active" does NOT mean the corresponding equality holds. It only means that the constraint must be satisfied in the model. The "equality" can hold or NOT hold.
For example, the optimal solution may be got by making constraint 1 and 2 must be satisfied. But, constraint 3 does not need to be satisfied.
How many of candidate constraints are active depends on the objective optimization value.
I know this may have exponential complexity because for 3 candidates, I can have 2^3 = 8 combinations of constraints.
Are there some ways to put all candidate in the model and solve it for one run to get the optimal solution and let the model decide which candidates should be active ?
thanks
If active means the equality holds:
Start by adding non negative slack variables $e_i$ to your model: $$ x_1+x_2+e_1=29\\ x_1-x_2+e_2=5\\ x_2+x_3+e_3=56 $$
Then, add binary variables $y_i$ that equal $1$ if and only if the slack variables $e_i$ take value $0$: $$ e_1\le M(1-y_1)\\ e_2\le M(1-y_2)\\ e_3\le M(1-y_3)\\ $$ Here, $M$ is a large constant, e.g., $56$.
Finally, impose that at least one constraint is active (i.e., one slack variable equals $0$, or one binary variable equals $1$): $$ y_1+y_2+y_3\ge 1 $$
If active means the constraint is satisfied:
Consider binary variables $y_i$ that equal $1$ if and only if constraint $i$ is satisfied and add the following constraints:
$$ x_1+x_2\le 29+M(1-y_1)\\ x_1-x_2\le5+M(1-y_2)\\ x_2+x_3\le56+M(1-y_3)\\ y_1+y_2+y_3\ge 1 $$