AXM001@gmail.com wrote:

Well, I cannot see how increasing the RHS in some of the constraints
will help solving the problem at all.

sum(j, a1(j)*x(j)) <= b1 + M1
sum(j, a2(j)*x(j)) <= b2 + M2

In case you did missunderstand my initial question, I guess I can be a
little more specific. What I want, is to solve an MLP problem were you
have subsets of constraints were only one constraint in each subset
needs to be satisfied. You can solve the problem by enumerating the
different variations of the problem.

Let c[X,Y] be a constraint Y that belongs to subset X. Let's say that I
have the following constraints in my problem: c[1,1] c[2,1] c[3,1]
c[3,2] c[4,1] c[4,2] c[4,3]. To solve this problem by enumerating all
possibillities I will have to solve 6 (2x3) LP problems in total.
problem will include the constraints: c[1,1] c[2,1] c[3,1] c[4,1], and
another c[1,1] c[2,1] c[3,1] c[4,2].

So what I really want is a way to get around this enumeration, since it
will make problems just a little bit larger pretty much intractable.

What I'm about to say is functionally identical to what Erwin posted,
although my notation may be a bit different. Perhaps a different
phrasing will help. I'm assuming, by the way, that there is no harm in
satisfying more than one constraint from a group.

Using your example, we'll start by introducing five 0-1 variables
y[3,1], y[3,2], y[4,1], y[4,2], y[4,3], where y[i,j] is 1 if you satisfy
c[i,j] and 0 otherwise. (I'm skipping y[1,1] and y[2,1] because you
know you have to satisfy c[1,1] and c[2,1].) To guarantee that at least
one constraint in each group is satisfied, we will assert the following
constraints:

c[1,1]
c[2,1]
y[3,1] + y[3,2] >= 1
y[4,1] + y[4,2] + y[4,3] >= 1

What remains is to connect y[3,1] to c[3,1], etc. Let's assume that
c[3,1] has the form a'x <= b (coefficient vector a, variable vector x).
We need to find a way to express the following:

if y[3,1] = 1, then a'x <= b;
if y[3,1] = 0, then we don't care whether a'x <= b.

We achieve the "we don't care part" by changing the right-hand side of
the constraint to a'x <= b + M, where the number M is chosen so large
that we are confident b + M is bigger than any value of a'x we're going
to see. For example, suppose a'x represents annual spending on parts by
a small manufacturer, and b is a budget of $100K (expressed in dollars,
i.e. 10^5). I'm pretty sure our small manufacturer is unlikely to spend
more than $1 trillion annually on parts, so M=10^12 should do the job,
although it's probably overkill.

So rather than enforce

c[3,1]: a'x <= b,

we enforce the following:

a'x <= b + M(1-y[3,1]).

If y[3,1] = 0, the right side is b + M, and we've chosen M large enough
that this has no effect on x (every reasonable x satisfies the
constraint). the other hand, if y[3,1] = 1, then the right side is
b, and we have enforced the original c[3,1].

Do the same for c[3,2], c[4,1], etc., where of course a and b change for
each constraint, and you may need to pick different constants M for
different constraints. You can use one really big M for all the
constraints, but it slows solution down.

The tricky part is in the choice of M. In each optional constraint, you
have to make M large enough so that, when it gets multiplied by 1, it
makes the constraint vacuous. the other hand, when you solve the
problem by branch-and-cut, the larger M is, the weaker the bounds you
get, and so nodes don't get fathomed as easily, and the solution process
drags on.

I hope that clarifies things a bit.
-- Paul