Constraint Satisfaction Problems (CSP) -------------------------------------- CSPs focus on finding any solution that satisfies all constraints without optimizing any particular objective. They are the foundation for more complex problem types. When to Use CSP ~~~~~~~~~~~~~~~ * Finding feasible solutions to complex constraint systems * Scheduling problems where any valid schedule is acceptable * Configuration problems with multiple requirements * Preprocessing to check problem feasibility Key Characteristics ~~~~~~~~~~~~~~~~~~ * **Variables**: Decision variables with bounds and types * **Constraints**: Linear and special constraints that must be satisfied * **No Objective**: Focus on feasibility, not optimality * **Solution**: Any point that satisfies all constraints .. code-block:: python from problem import OXCSPProblem from constraints import RelationalOperators # Create CSP for employee scheduling csp = OXCSPProblem() # Variables: work assignments (binary) days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri'] shifts = ['Morning', 'Evening'] employees = ['Alice', 'Bob', 'Carol'] for employee in employees: for day in days: for shift in shifts: csp.create_decision_variable( var_name=f"{employee}_{day}_{shift}", description=f"{employee} works {shift} on {day}", lower_bound=0, upper_bound=1, variable_type="binary" ) # Constraint: Each shift must be covered for day in days: for shift in shifts: shift_vars = [ var.id for var in csp.variables if f"{day}_{shift}" in var.name ] csp.create_constraint( variables=shift_vars, weights=[1] * len(shift_vars), operator=RelationalOperators.GREATER_THAN_EQUAL, value=1, description=f"Cover {shift} shift on {day}" ) # Constraint: No employee works both shifts same day for employee in employees: for day in days: morning_var = next(v for v in csp.variables if f"{employee}_{day}_Morning" in v.name) evening_var = next(v for v in csp.variables if f"{employee}_{day}_Evening" in v.name) csp.create_constraint( variables=[morning_var.id, evening_var.id], weights=[1, 1], operator=RelationalOperators.LESS_THAN_EQUAL, value=1, description=f"{employee} works at most one shift on {day}" ) .. raw:: html

Linear Programming (LP) ----------------------- Linear Programming extends CSP by adding an objective function to optimize. LP problems seek to maximize or minimize a linear objective subject to linear constraints. When to Use LP ~~~~~~~~~~~~~~ * Resource allocation with clear optimization goals * Production planning to maximize profit or minimize cost * Transportation problems minimizing shipping costs * Portfolio optimization with linear objectives Key Characteristics ~~~~~~~~~~~~~~~~~~ * **Variables**: Continuous, integer, or binary decision variables * **Constraints**: Linear equality and inequality constraints * **Objective**: Single linear objective function (minimize or maximize) * **Solution**: Optimal point that maximizes/minimizes the objective Mathematical Form ~~~~~~~~~~~~~~~~ .. math:: \begin{align} \text{minimize/maximize} \quad & \sum_{i=1}^{n} c_i x_i \\ \text{subject to} \quad & \sum_{i=1}^{n} a_{ji} x_i \leq b_j, \quad j = 1, \ldots, m \\ & x_i \geq 0, \quad i = 1, \ldots, n \end{align} Where: - :math:`x_i` are decision variables - :math:`c_i` are objective coefficients - :math:`a_{ji}` are constraint coefficients - :math:`b_j` are constraint bounds .. code-block:: python from problem import OXLPProblem, ObjectiveType from constraints import RelationalOperators # Create LP for production planning lp = OXLPProblem() # Products to manufacture products = [ {'name': 'Product_A', 'profit': 50, 'labor': 2, 'material': 1}, {'name': 'Product_B', 'profit': 40, 'labor': 3, 'material': 2}, {'name': 'Product_C', 'profit': 60, 'labor': 1, 'material': 3} ] # Create production variables for product in products: lp.create_decision_variable( var_name=f"production_{product['name']}", description=f"Units of {product['name']} to produce", lower_bound=0, upper_bound=1000, variable_type="continuous" ) # Resource constraints # Labor constraint: total labor <= 1000 hours labor_vars = [var.id for var in lp.variables] labor_weights = [product['labor'] for product in products] lp.create_constraint( variables=labor_vars, weights=labor_weights, operator=RelationalOperators.LESS_THAN_EQUAL, value=1000, description="Labor hours constraint" ) # Material constraint: total material <= 800 units material_weights = [product['material'] for product in products] lp.create_constraint( variables=labor_vars, # Same variables weights=material_weights, operator=RelationalOperators.LESS_THAN_EQUAL, value=800, description="Material constraint" ) # Objective: maximize total profit profit_weights = [product['profit'] for product in products] lp.create_objective_function( variables=labor_vars, weights=profit_weights, objective_type=ObjectiveType.MAXIMIZE ) # Solve the problem from solvers import solve status, solution = solve(lp, 'ORTools') .. raw:: html

Goal Programming (GP) --------------------- Goal Programming handles multiple, often conflicting objectives by formulating them as goals with associated deviation variables and priorities. When to Use GP ~~~~~~~~~~~~~~ * Multi-criteria decision making * Problems with conflicting objectives * Situations where trade-offs are necessary * When exact goal achievement is less important than minimizing deviations Key Characteristics ~~~~~~~~~~~~~~~~~ * **Variables**: Decision variables plus deviation variables * **Constraints**: Regular constraints plus goal constraints * **Objectives**: Multiple goals with priorities or weights * **Solution**: Minimize weighted deviations from goals Mathematical Form ~~~~~~~~~~~~~~~~ .. math:: \begin{align} \text{minimize} \quad & \sum_{i=1}^{k} w_i^+ d_i^+ + w_i^- d_i^- \\ \text{subject to} \quad & \sum_{j=1}^{n} a_{ij} x_j + d_i^- - d_i^+ = g_i, \quad i = 1, \ldots, k \\ & \text{regular constraints} \\ & x_j, d_i^+, d_i^- \geq 0 \end{align} Where: - :math:`d_i^+, d_i^-` are positive and negative deviation variables - :math:`w_i^+, w_i^-` are weights for deviations - :math:`g_i` are goal targets .. code-block:: python from problem import OXGPProblem from constraints import RelationalOperators # Create GP for workforce planning gp = OXGPProblem() # Decision variables: number of employees to hire departments = ['Engineering', 'Sales', 'Support'] for dept in departments: gp.create_decision_variable( var_name=f"hire_{dept}", description=f"Employees to hire in {dept}", lower_bound=0, upper_bound=50, variable_type="integer" ) # Goal constraints with priorities goals = [ { 'description': 'Total workforce target of 100 employees', 'variables': [var.id for var in gp.variables], 'weights': [1, 1, 1], 'target': 100, 'priority': 1 }, { 'description': 'Engineering should be 40% of workforce', 'variables': [gp.variables[0].id], # Engineering 'weights': [1], 'target': 40, 'priority': 2 }, { 'description': 'Balance between Sales and Support', 'variables': [gp.variables[1].id, gp.variables[2].id], # Sales, Support 'weights': [1, -1], 'target': 0, # Equal hiring 'priority': 3 } ] # Add goal constraints for goal in goals: gp.create_goal_constraint( variables=goal['variables'], weights=goal['weights'], target_value=goal['target'], description=goal['description'] ) # Additional regular constraints # Budget constraint: hiring costs <= $500,000 hiring_costs = [80000, 60000, 50000] # Cost per hire by department gp.create_constraint( variables=[var.id for var in gp.variables], weights=hiring_costs, operator=RelationalOperators.LESS_THAN_EQUAL, value=500000, description="Budget constraint" ) .. raw:: html

Aspect	CSP	LP	GP
Primary Goal	Find feasible solution	Optimize single objective	Balance multiple objectives
Objective Function	None	Single linear objective	Multiple goals with priorities
Solution Type	Any feasible point	Optimal point	Best compromise point
Complexity	Low	Medium	High
Use Cases	Scheduling, Configuration	Resource allocation, Planning	Multi-criteria decisions

Choose CSP When:

Choose LP When:

Choose GP When: