A constraint restricts the values or combinations of values that decision variables may take. In optimization, the objective function says what to improve; constraints say which solutions are admissible. The feasible search space contains solutions that satisfy the required constraints. A feasible solution need not be optimal: it may still have a worse objective value than another feasible solution. section 1.3 section 1.3.3
Specify what each restriction means before choosing a solution method:
- Boundary constraints limit each variable’s domain. Equality constraints require an exact relationship; inequality constraints impose a limit. section 1.3.3
- Hard constraints must be satisfied. In a school timetable, two lectures cannot use the same room at the same time, and a teacher cannot teach two lectures at once. section 1.3.3
- Soft constraints express preferences rather than requirements. Nearby rooms for back-to-back lectures and avoiding very early or late classes are timetable preferences. A reward or penalty in the objective function can account for them. section 1.3.3
Ticket sales with an exact total
Let x be in-person ticket sales and y be virtual ticket sales. With 10,000 welcome packages and a goal of filling the event, impose x + y = 10,000 while maximizing profit. A SymPy implementation forms a Lagrange expression from the profit function and this equality, differentiates it, and solves the resulting equations for x, y, and the multiplier. This is a worked method for the equality-constrained version of the problem, not a reason to treat every preference as mandatory. section 2.1.3
Listing 2.5 Maximizing profits using Lagrange multipliers
import sympy as sym
x,y=sym.var('x, y', positive=True) #1
f=155*x+(0.001*x**sym.Rational(3,2)+70)*y-1000000 #2
g=x+y-10000 #3
lamda=sym.symbols('lambda') #4
Lagr=f-lamda*g #5
eqs = [sym.diff(Lagr, x), sym.diff(Lagr, y), g] #6
sol=sym.solve(eqs,[x,y,lamda], dict=True) #7
def getValueOf(k, L):
for d in L:
if k in d:
return d[k]
profit=[f.subs(p) for p in sol]
print("optimal number of physical ticket sales: x = %.0f" % getValueOf(x, sol))
print("optimal number of online ticket sales: y = %.0f" % getValueOf(y, sol))
print("Expected profil: f(x,y) = $%.4f" % profit[0])
Inspect the SymPy listing to see where the ticket-total equality enters the Lagrange expression and the equations passed to the solver. section 2.1.3
Sometimes the aim is only to satisfy constraints: the n-queens problem has no explicit objective function and asks for placements with no shared row, column, or diagonal. When preferences are soft, inspect the resulting trade-off instead. In the cargo-bike example, exceeding capacity incurs a penalty of 50, so an overweight selection can still be considered by the model rather than ruled out outright. section 1.3.2 section 1.3.3
