Articulating categorical soft constraints in MILP

Question

I'm curious how is the best way to articulate a soft, categorical constraint for MILP solvers.

In example, say that there are two sizes of t-shirts, small and large. Likewise, people have ideal t-shirt sizes, small and large. A hard constraint would enforce that everybody gets a t-shirt their size and if that's not possible, there is no solution.

Conversely, a soft constraint would enforce that everybody received a t-shirt, but it might not be their ideal size. I believe that this could be done by an objective term, rather than a constraint, by maximizing the number of people who got their ideal t-shirt size (or minimizing those who didn't.)

However, I'd like to some feedback on how I can express this categorical soft constraint in terms of variables, which a generic MILP solver would accept.

Answer 1

One approach is to use penalty terms. So you would have variables for number of small/large shirts delivered to customers asking for small/large shirts (four variables, one for each combination), constraints that small shirts delivered to customers who wanted them plus small shirts delivered to customers who wanted large equals total small shirts produced (and similarly for large shirts), and penalty terms in the objective for each small (large) shirt delivered to a customer requesting a large (small) shirt. These penalties need not be equal. Sending a big person a small shirt may be worse than sending a small person a big shirt. Adding penalties is easy in formulation terms; the tricky part is picking the right values (objective coefficients) for the penalties.

Another approach is to constrain the number of small (large) shirts used to satisfy demand for large (small) shirts, specifying upper limits. A third approach is to use both constraints and penalties (penalties to discourage mismatches and constraints to make sure that at most a certain number of angry customers of either type is created, even if it means eating larger penalties).

With regard to penalties, sometimes it is useful to apply a sequence of progressively more stringent penalties for the same constraint violation. For instance, suppose I have a variable that assigns work hours to a worker who has a nominal 40 hour work week. I might write the constraint as "hours assigned - slack + OT1 + OT2 = 40," where OT1 is "time-and-a-half overtime" (lower bound 0, upper bound 10, penalty coefficient = 1.5 times normal wage) and OT2 is "double-time overtime" (lower bound 0, no upper bound, penalty coefficient = 2 times normal wage).