2.6 Useful Modeling Techniques

So far, we have discussed the kinds of optimization problems that can be solved and certain methods available for solving them. Practical success, however, depends upon the effective translation and formulation of a problem description into a mathematical programming problem, which often turns out to be as much an art as it is a science.

We will not be discussing formulation techniques in detail (see [23] for a deep dive into the topic) – instead, we highlight modeling techniques that often arise in business applications, which our examples have not covered so far.

2.6.1 Activation

Sometimes, we may want to set a binary variable \(y\) to 1 whenever some other variable \(x\) is positive. Assuming that \(x\) is bounded above by \(M\), the inequality \[x \leq My\] will model the condition. Note that if there is no valid upper bound on \(x\), the condition cannot be modeled using a linear constraint.

2.6.2 Disjunction

Sometimes, we want \(\mathbf{x}\) to satisfy at least one of a list of inequalities; that is, \[{\mathbf{a}^{(1)}}^\mathsf{T}\mathbf{x} \geq b_1 \lor {\mathbf{a}^{(2)}}^\mathsf{T}\mathbf{x} \geq b_2 \lor \cdots \lor {\mathbf{a}^{(k)}}^\mathsf{T}\mathbf{x} \geq b_k.\] To formulate such a disjunction using linear constraints, we assume that, for \(i = 1,\ldots,k\), there is a lower bound \(M_i\) on \({\mathbf{a}^i}^\mathsf{T}\mathbf{x}\) for all \(\mathbf{x}\in \mathcal{D}\). Note that such bounds automatically exist when \(\mathcal{D}\) is a bounded set, which is often the case in applications.

The disjunction can now be formulated as the following system where \(y_i\) is a new 0-1 variable for \(i = 1,\ldots,k\): \[\begin{array}{|l} {\mathbf{a}^{(1)}}^\mathsf{T}\mathbf{x} \geq b_1 y_1 + M_1(1-y_1) \\ {\mathbf{a}^{(2)}}^\mathsf{T}\mathbf{x} \geq b_2 y_2 + M_2(1-y_2) \\ \qquad\quad \vdots \\ {\mathbf{a}^{(k)}}^\mathsf{T}\mathbf{x} \geq b_k y_k + M_k(1-y_k) \\ y_1 + \cdots + y_k \geq 1. \end{array}\]

Note that \({\mathbf{a}^i}^\mathsf{T}\mathbf{x} \geq b_i y_i + M_i(1-y_i)\) reduces to \({\mathbf{a}^i}^\mathsf{T}\mathbf{x} \geq b_i\) when \(y_i = 1\), and to \({\mathbf{a}^i}^\mathsf{T}\mathbf{x} \geq M_i\) when \(y_i = 0\), which holds for all \(\mathbf{x} \in \mathcal{D}.\)

Therefore, \(y_i\) is an activation for the \(i^{\textrm{th}}\) constraint, and at least one is activated because of the constraint \[y_1 + \cdots + y_k \geq 1.\]

2.6.3 Soft Constraints

Sometimes, we may be willing to pay a price in exchange for specific constraints to be violated (perhaps they represent “nice-to-have” conditions instead of “must-be-met” conditions). Such constraints are referred to as soft constraints.

There are situations in which having soft constraints is advisable, say when enforcing all constraints results into an infeasible problem, but a solution is nonetheless needed.

We illustrate the idea on a modified BKP. As usual, there are \(n\) items and item \(i\) has weight \(w_i\) and value \(v_i>0\) for \(i = 1,\ldots, n\). The capacity of the knapsack is denoted by \(K\). Suppose that we prefer not to take more than \(N\) items, but that the preference is not an actual constraint.

We assign a penalty for its violation and use the following formulation: \[\begin{array}{|rl} \max & \sum\limits_{i = 1}^n v_i x_i - p y\\ \mbox{s.t.} & \sum\limits_{i = 1}^n w_i x_i \leq K \\ & \sum\limits_{i = 1}^n x_i - y \leq N \\ & x_i \in \{0,1\} \quad i = 1,\ldots, n \\ & y \geq 0. \end{array}\]

Here, \(p\) is a non-negative number of our choosing. As we are maximizing \[\sum\limits_{i = 1}^n v_i x_i - p y,\] \(y\) is pushed towards 0 when \(p\) is relatively large. Therefore, the problem will be biased towards solutions that try to violate \(x_1+\cdots+x_n \leq N\) as little as possible.

Experimentation is required to determine What value to select for \(p\); the general rule is that if violation is costly in practice, we should set \(p\) to be (relatively) high; otherwise, we set it to a moderate value relative to the coefficients of the variables in the objective function value.

Note that when \(p=0\) , the constraint \(x_1+\cdots+x_n \leq N\) has no effect because \(y\) can take on any positive value without incurring a penalty.

References

[23]
H. P. Williams, “Model building in linear and integer programming,” in Computational mathematical programming, 1985, pp. 25–53.