Lecture Notes on Linear and Integer Programming: Constraints and Modeling

Author

Your Name

Published

January 30, 2025

Introduction

This lecture delves into the crucial aspect of formulating constraints in linear and integer programming models. We will explore various types of variables and how to represent different kinds of constraints, from basic linear inequalities to more complex logical conditions. The focus will be on transforming real-world problems into mathematical models suitable for optimization, emphasizing the use of binary variables to model logical operations and piecewise linear functions. We will also discuss advanced techniques like the Big M method for handling disjunctions and modeling non-convex feasible regions, and finally touch upon the concepts of model size, complexity, and implicit models.

Variables and Constraints

Types of Variables

In mathematical programming, selecting the right types of variables is fundamental to accurately model real-world problems. We primarily deal with two types of variables: numerical and binary.

Numerical Variables

Numerical variables, also known as continuous variables, can take any real value within a defined range.

Numerical variables are used to represent quantities that can be measured on a continuous scale, such as production levels, amounts of resources, or time.

Binary Variables

Binary variables, also known as 0-1 variables, can only take two values: 0 or 1.

They are essential for modeling yes/no decisions, logical conditions, and discrete choices. In the context of logic, 1 is often associated with ‘true’ and 0 with ‘false’.

Linear Constraints

A linear constraint is a restriction on variables expressed as a linear inequality or equality.

Constraints are restrictions or conditions that limit the possible values of the variables in a model. In linear programming, these constraints are linear inequalities or equalities. A general form of a linear constraint is given by:

\[a_1x_1 + a_2x_2 + \dots + a_nx_n \geq B \quad \text{or} \quad a_1x_1 + a_2x_2 + \dots + a_nx_n \leq B\]

where $x_1, x_2, \dots, x_n$ are variables, and $a_1, a_2, \dots, a_n, B$ are constants. Linear equations are also valid constraints in linear programming, and importantly, a linear equation can be represented by two linear inequalities. For example, $ax = b$ is equivalent to $ax \geq b$ and $ax \leq b$. Thus, linear inequalities are the fundamental building blocks of constraints in linear programming.

Piecewise Linear Constraints

A piecewise linear constraint involves functions that are linear in segments.

Piecewise linear constraints involve functions that are linear in segments. These can model situations where costs or values change at different thresholds.

Linearization using Binary Variables

Piecewise linear constraints can be linearized and incorporated into linear programming models by introducing binary variables. This technique allows us to handle non-linearities that arise from piecewise linear functions within the framework of linear programming. The exact method for linearization depends on the specific form of the piecewise linear function, and often involves introducing binary variables to select which linear segment is active. (Detail missing: teacher explanation unclear on specific linearization methods, further examples would be beneficial).

Linear Inequalities

A linear inequality is a constraint of the form $a_1x_1 + a_2x_2 + \dots + a_nx_n \geq B$ or $a_1x_1 + a_2x_2 + \dots + a_nx_n \leq B$.

Linear inequalities are the cornerstone of constraints in linear programming and integer programming. They define the feasible region within which the optimal solution must lie.

Basic Forms

Linear inequalities come in two basic forms, and equations can be represented using a combination of these.

Greater Than or Equal To ($\geq$)

The "greater than or equal to" inequality, denoted as $\geq$, specifies a minimum requirement or lower bound. It ensures that a linear combination of variables is at least a certain value.

Less Than or Equal To ($\leq$)

The "less than or equal to" inequality, denoted as $\leq$, specifies a maximum limit or upper bound. It ensures that a linear combination of variables does not exceed a certain value.

Representing Linear Equations with Inequalities

A linear equation $LHS = RHS$ can be represented by two linear inequalities: $LHS \geq RHS$ and $LHS \leq RHS$. This shows that inequalities are sufficient to express both inequality and equality constraints in linear programming.

Coefficients and Constants

In a linear inequality, coefficients (the $a_i$s) and constants (like $B$) are real numbers. These values are parameters of the problem and are fixed. They define the slope and intercept of the hyperplanes that bound the feasible region.

Non-Negativity Constraints

A non-negativity constraint is a linear inequality of the form $x_i \geq 0$.

Non-negativity constraints are a common type of linear inequality, often written as $x_i \geq 0$. They restrict variables to be non-negative, which is natural in many real-world applications where variables represent physical quantities that cannot be negative (e.g., production quantity, amount of resource). These constraints are indeed a special case of the general linear inequality form, where for $x_1 \geq 0$, we can write it as $1 \cdot x_1 + 0 \cdot x_2 + \dots + 0 \cdot x_n \geq 0$.

Interpretation of Inequalities

Linear inequalities can be interpreted in various ways depending on the context of the problem.

Guaranteeing Minimum Levels (using $\geq$)

Inequalities of the form $\sum_{i} a_ix_i \geq B$ are often used to guarantee a minimum level of some requirement. This could represent ensuring a minimum production quantity, meeting dietary requirements, or maintaining a certain service level.

Example: Dietary Requirements

Consider formulating a dietary plan to meet a minimum sugar intake. Let $x_1$ be the number of apples, $x_2$ be the amount of bread (in hectograms), and $x_3$ be the amount of peas (in hectograms) consumed daily. Suppose an apple contains 19g of sugar, 100g of bread contains 5g of sugar, and 100g of peas contains 6g of sugar. If the minimum daily sugar requirement is 30g, the constraint can be written as:

\[19x_1 + 5x_2 + 6x_3 \geq 30\]

This inequality ensures that the total sugar intake from apples, bread, and peas is at least 30g. Additional constraints, such as an upper limit on sugar intake, could also be added using $\leq$ inequalities.

Variable Bounds

Variable bounds are linear inequalities that define the permissible range for individual variables, such as $l_i \leq x_i \leq u_i$.

Variable bounds are simple linear inequalities that define the range within which a variable must lie.

Lower and Upper Bounds

For a variable $x_i$, we can set a lower bound $l_i$ and an upper bound $u_i$ such that $l_i \leq x_i \leq u_i$. This is equivalent to two separate inequalities: $x_i \geq l_i$ and $x_i \leq u_i$. For instance, if we need to decide the number of pencils $x_i$ to purchase, and we must buy at least 20 but no more than 50, we would have $20 \leq x_i \leq 50$.

Forcing Relationships Between Variables

Linear inequalities are powerful tools for modeling logical relationships and dependencies between variables, especially when binary variables are involved.

Logical Implications

Linear inequalities can enforce logical implications between variables. For example, to model "if condition A is true, then condition B must be true," we can use inequalities involving binary variables representing the truth values of conditions A and B.

Boolean Conditions

Boolean conditions, such as AND, OR, NOT, XOR, and implications, can be translated into linear inequalities, particularly when working with binary variables. This allows us to integrate logical constraints into linear and integer programming models.

Loose vs. Non-Trivial Constraints

When formulating constraints, it’s important to understand whether a constraint is actually restricting the feasible region or if it is redundant.

Definition of Loose Constraints

A constraint is considered loose if it is always satisfied whenever all other constraints are met.

A constraint is considered loose or redundant for a given assignment of variables if it is always satisfied by any feasible solution that meets all other constraints, especially around a specific variable assignment. Adding a loose constraint does not reduce the feasible region.

Definition of Non-Trivial (Tight) Constraints

A constraint is considered non-trivial (tight) if it actively limits the feasible region.

A constraint is non-trivial or tight (or binding) for a given assignment of variables if it effectively restricts the feasible region. For certain variable assignments, a tight constraint can become critical in determining the feasibility of a solution. Adding a tight constraint can reduce the feasible region.

Conditional Tightness

Constraints can be conditionally tight, meaning they are loose under certain conditions (assignments of some variables) and tight under others. This property is particularly useful for modeling logical implications and conditional decisions. We aim to design constraints that are loose in most cases but become tight to enforce specific relationships when certain conditions are met.

Examples

Let’s look at some examples to illustrate the concepts of loose and tight constraints.

Example 1: $z \leq x + y$

Consider the constraint $z \leq x + y$, where $x, y, z$ are binary variables. This constraint is loose for all combinations of $(x, y)$ except when $x = 0$ and $y = 0$.

If $x=1$ or $y=1$, then $x+y \geq 1$, so $z \leq x+y$ becomes $z \leq 1$ or $z \leq 2$, which is always true for a binary variable $z \in \{0, 1\}$.
If $x=0$ and $y=0$, then $x+y = 0$, so $z \leq x+y$ becomes $z \leq 0$. Since $z$ is binary and non-negative, this forces $z = 0$.

Logically, this constraint can be interpreted as: if $(x \lor y)$ is false (i.e., both $x$ and $y$ are false), then $z$ must be false. In Boolean logic terms: $(\neg x \land\neg y) \implies \neg z$.

Example 2: $x \leq 20 - 15y$

Consider the constraint $x \leq 20 - 15y$, where $x$ is a real variable with an existing upper bound $x \leq 10$, and $y$ is a binary variable.

If $y = 0$, the constraint becomes $x \leq 20$. Since we already have $x \leq 10$, the constraint $x \leq 20$ is loose and redundant.
If $y = 1$, the constraint becomes $x \leq 20 - 15 = 5$. In this case, $x \leq 5$ is a tight constraint, which is more restrictive than the original bound $x \leq 10$.

This constraint models a situation where the upper bound on $x$ depends on the value of the binary variable $y$. If $y$ is true (1), the bound on $x$ is tightened to 5; if $y$ is false (0), the bound remains effectively at 10 (considering the pre-existing constraint). We could also rewrite the constraint as $x \leq 10 - 5y$ to directly see that when $y=0$, $x \leq 10$, and when $y=1$, $x \leq 5$.

Logical Operations with Constraints

Linear inequalities can be used to model various logical operations, which is crucial for formulating complex decision-making problems within linear and integer programming.

Logical OR

The logical OR operation ($\lor$) is true if at least one of the operands is true.

Ensuring at Least One Variable is True

To ensure that at least one of the binary variables $x_1, x_2, \dots, x_n$ is true (i.e., at least one is equal to 1), we can use the following constraint:

\[x_1 + x_2 + \dots + x_n \geq 1\]

This inequality forces the sum of the variables to be at least 1, which means at least one variable must be 1.

Covering Constraints

A covering constraint is of the form $\sum_{i} x_i \geq 1$, ensuring at least one variable is true.

A constraint of the form $\sum_{i} x_i \geq 1$ is also known as a covering constraint, as it ensures that at least one variable "covers" the condition of being true.

Logical OR as a Variable

Sometimes, we need a binary variable $z$ to represent the logical OR of several other binary variables $x_1, x_2, \dots, x_n$. We want $z$ to be 1 if $x_1 \lor x_2 \lor\dots \lor x_n$ is true, and 0 otherwise.

Constraints for $z = x_1 \lor x_2 \lor\dots \lor x_n$

To model $z = x_1 \lor x_2 \lor\dots \lor x_n$, we use $n+1$ linear inequalities.

To model $z = x_1 \lor x_2 \lor\dots \lor x_n$, we can use the following set of constraints:

\[\begin{aligned} z &\leq x_1 + x_2 + \dots + x_n \\ z &\geq x_i \quad \text{for all } i = 1, 2, \dots, n \end{aligned}\]

The constraint $z \leq x_1 + x_2 + \dots + x_n$ ensures that if all $x_i$s are 0, then $z$ must be 0. If at least one $x_i$ is 1, this constraint becomes loose (since $z \leq \sum x_i$ will be $z \leq 1$ or greater, which is always true for binary $z$).
The constraints $z \geq x_i$ for all $i$ ensure that if any $x_i$ is 1, then $z$ must also be 1. If all $x_i$s are 0, these constraints become $z \geq 0$, which is naturally satisfied for a binary variable.

In total, we use $n+1$ linear inequalities to model the OR operation as a variable.

Logical XOR

The logical XOR operation ($\oplus$) is true if exactly one of the operands is true.

Constraints for $z = x \oplus y$

To model $z = x \oplus y$, we can use 4 linear inequalities or 1 equation with 1 additional binary variable.

To model $z = x \oplus y$, where $z, x, y$ are binary variables, we can use the following set of inequalities:

\[\begin{aligned} z &\leq x + y \\ z &\leq 2 - x - y \\ z &\geq x - y \\ z &\geq y - x \end{aligned}\]

Let’s analyze these constraints:

$z \leq x + y$: If $x=0$ and $y=0$, then $z \leq 0$, forcing $z=0$.
$z \leq 2 - x - y$: If $x=1$ and $y=1$, then $z \leq 2 - 1 - 1 = 0$, forcing $z=0$.
$z \geq x - y$ and $z \geq y - x$: These two together ensure that if exactly one of $x$ or $y$ is 1, then $z \geq 1$, forcing $z=1$. For instance, if $x=1, y=0$, $z \geq 1-0=1$ and $z \geq 0-1=-1$ (loose). If $x=0, y=1$, $z \geq 0-1=-1$ (loose) and $z \geq 1-0=1$.

These four inequalities together correctly define $z = x \oplus y$.

Alternative Formulation with an Additional Variable

Another way to model $z = x \oplus y$ is using a single equation but with an additional binary variable $w$:

\[z = x + y - 2w\] where $w$ is a binary variable. This formulation ensures that $z$ has the same parity as $x + y$.

If $x+y = 0$ or $x+y = 2$ (both 0 or both 1), then $x+y$ is even, and to make $z$ binary and have the same parity, $z$ must be 0.
If $x+y = 1$ (one is 0 and the other is 1), then $x+y$ is odd, and to make $z$ binary and have the same parity, $z$ must be 1.

Logical XOR as a Constraint

Sometimes, we need to impose a constraint that the XOR of two or more variables must be true.

Ensuring Exactly One Variable is True

To ensure exactly one of $x_1, x_2, \dots, x_n$ is true, we use 1 linear equation.

To ensure that exactly one of the binary variables $x_1, x_2, \dots, x_n$ is true, we use the constraint:

\[x_1 + x_2 + \dots + x_n = 1\]

This equation forces the sum of the variables to be exactly 1, meaning precisely one variable must be 1, and all others must be 0.

Partitioning/Selection Constraints

A partitioning/selection constraint is of the form $\sum_{i} x_i = 1$, ensuring exactly one variable is true.

Constraints of the form $\sum_{i} x_i = 1$ are known as partitioning or selection constraints. They are used when we need to select exactly one option out of several mutually exclusive choices.

Assignment Constraints

Assignment constraints are a specific application of selection constraints, particularly useful in problems involving assigning items to categories or tasks.

Permutation Matrices

A permutation matrix is a square matrix where each row and each column has exactly one entry equal to 1, and all other entries are 0.

To ensure a matrix is a permutation matrix, we use $2N$ linear equations for $N^2$ variables.

Consider a set of binary variables $x_{ij}$ where $i, j \in \{1, 2, \dots, N\}$. The constraints:

\[\begin{aligned} \sum_{j=1}^{N} x_{ij} &= 1 \quad \text{for all } i = 1, 2, \dots, N \\ \sum_{i=1}^{N} x_{ij} &= 1 \quad \text{for all } j = 1, 2, \dots, N \end{aligned}\]

These constraints together ensure that the matrix $X = (x_{ij})$ is a permutation matrix. The first set of constraints ensures that for each row $i$, exactly one $x_{ij}$ is 1. The second set ensures that for each column $j$, exactly one $x_{ij}$ is 1. This structure is fundamental in assignment problems and problems involving permutations, such as the Traveling Salesperson Problem (TSP). In TSP, these constraints can be part of the formulation to ensure that each city is visited exactly once and left exactly once in a tour.

Logical AND

The logical AND operation ($\land$) is true if and only if all operands are true.

Constraints for $z = x \land y$

To model $z = x \land y$, we use 3 linear inequalities. To model $z = x_1 \land x_2 \land\dots \land x_n$, we use $n+1$ linear inequalities.

To model $z = x \land y$, where $z, x, y$ are binary variables, we can use the following set of inequalities:

\[\begin{aligned} z &\leq x \\ z &\leq y \\ z &\geq x + y - 1 \end{aligned}\]

$z \leq x$ and $z \leq y$: These ensure that if either $x=0$ or $y=0$, then $z$ must be 0.
$z \geq x + y - 1$: If $x=1$ and $y=1$, then $z \geq 1 + 1 - 1 = 1$, forcing $z=1$. If either $x$ or $y$ is 0, say $x=0$, then $z \geq 0 + y - 1 = y - 1$. Since $y \in \{0, 1\}$, $y-1$ is either -1 or 0, so $z \geq y-1$ becomes a loose constraint ($z \geq -1$ or $z \geq 0$, both are always true for binary $z$ as long as $z \geq 0$).

These three inequalities correctly define $z = x \land y$.

Constraints for $z = x_1 \land x_2 \land\dots \land x_n$

To generalize for $n$ variables, $z = x_1 \land x_2 \land\dots \land x_n$, we can use:

\[\begin{aligned} z &\leq x_i \quad \text{for all } i = 1, 2, \dots, n \\ z &\geq \sum_{i=1}^{n} x_i - (n - 1) \end{aligned}\]

$z \leq x_i$ for all $i$: Ensures $z=0$ if any $x_i=0$.
$z \geq \sum_{i=1}^{n} x_i - (n - 1)$: If all $x_i = 1$, then $z \geq n - (n - 1) = 1$, forcing $z=1$. If at least one $x_i = 0$, then $\sum_{i=1}^{n} x_i \leq n-1$, so $\sum_{i=1}^{n} x_i - (n - 1) \leq 0$, and $z \geq \sum_{i=1}^{n} x_i - (n - 1)$ becomes $z \geq 0$ or $z \geq \text{negative value}$, which is loose.

Logical NOT

The logical NOT operation ($\neg$) is true if the operand is false, and false if the operand is true.

Constraints for $y = \neg x$

To model $y = \neg x$, we use 1 linear equation.

To model $y = \neg x$, where $x, y$ are binary variables, we can simply use the equation:

\[y = 1 - x\]

If $x=1$, $y=0$; if $x=0$, $y=1$. This equation directly represents the NOT operation. In practice, if we need $\neg x$, we can often directly use $1-x$ in linear expressions instead of introducing a new variable $y$.

Logical Implication

The logical implication ($x \implies y$) is true if whenever $x$ is true, $y$ must also be true.

Constraints for $x \implies y$

To model $x \implies y$, we use 1 linear inequality.

To model $x \implies y$, where $x, y$ are binary variables, we can use the inequality:

\[y \geq x \quad \text{or equivalently } \quad y - x \geq 0\]

If $x=1$, then $y \geq 1$, forcing $y=1$. If $x=0$, then $y \geq 0$, which is always true for a binary variable, so $y$ can be either 0 or 1. This accurately models the implication.

Complex Logical Conditions

More complex logical conditions can be modeled by combining the basic logical operations we’ve discussed.

Example: If $x$ then $y \implies z$, else $y$ or $z$ are false

Consider the condition: "If $x$ is true, then ($y$ implies $z$), else ($y$ is false OR $z$ is false)". In logical notation: $(x \implies(y \implies z)) \land(\neg x \implies(\neg y \lor\neg z))$. We can analyze the truth table for this condition to derive constraints.

Analyzing the condition:

If $x = \text{true}$ (1), then $y \implies z$ must be true. $y \implies z$ is false only when $y = \text{true}$ and $z = \text{false}$ (1 and 0). So, if $x=1$, we must not have $y=1$ and $z=0$.
If $x = \text{false}$ (0), then $\neg y \lor\neg z$ must be true. This means it’s not allowed to have both $y = \text{true}$ and $z = \text{true}$ (1 and 1). So, if $x=0$, we must not have $y=1$ and $z=1$.

Forbidden configurations are $(x, y, z) = (1, 1, 0)$ and $(x, y, z) = (0, 1, 1)$.

Prohibiting Specific Bit Configurations

To prohibit a specific bit configuration of $n$ binary variables, we use 1 linear inequality.

To prohibit specific bit configurations, we can use linear inequalities. For $n$ binary variables $x_1, x_2, \dots, x_n$, to forbid a configuration $(b_1, b_2, \dots, b_n)$, we can use the constraint:

\[\sum_{i: b_i=1} x_i + \sum_{i: b_i=0} (1 - x_i) \leq n - 1\] For configuration $(1, 1, 0)$, i.e., $(x, y, z) = (1, 1, 0)$, we have $n=3$. Bits at positions 1 and 2 are 1, bit at position 3 is 0. So, the constraint is: $x + y + (1 - z) \leq 3 - 1 = 2$, which simplifies to $x + y - z \leq 1$. For configuration $(0, 1, 1)$, i.e., $(x, y, z) = (0, 1, 1)$, we have $n=3$. Bit at position 1 is 0, bits at positions 2 and 3 are 1. So, the constraint is: $(1 - x) + y + z \leq 3 - 1 = 2$, which simplifies to $-x + y + z \leq 1$.

Thus, the constraints to enforce the complex logical condition are: \[\begin{aligned} x + y - z &\leq 1 \\ -x + y + z &\leq 1 \end{aligned}\]

Variable Ranges

Constraints can also be used to define the permissible ranges for variables, which can be continuous or disjoint.

Lower and Upper Bounds

As discussed earlier, lower and upper bounds $l_i \leq x_i \leq u_i$ define a continuous range for variable $x_i$.

Disjoint Ranges

Sometimes, we need to model situations where a variable can take values from disjoint ranges. For example, a variable $x$ can be either 0 or in the range $[L, U]$, where $L > 0$. This creates a non-convex feasible region.

Modeling with an Additional Binary Variable

To model disjoint ranges like $x=0$ or $L \leq x \leq U$, we use 3 linear inequalities and introduce 1 additional binary variable.

To model disjoint ranges like $x=0$ or $L \leq x \leq U$, we can introduce a binary variable $y \in \{0, 1\}$ and use the following constraints:

\[\begin{aligned} x &\geq L \cdot y \\ x &\leq U \cdot y \\ x &\geq 0 \end{aligned}\] If $y=1$, then\[\begin{aligned} x &\geq L \cdot y \\ x &\leq U \cdot y \\ x &\geq 0 \end{aligned}\] If $y=1$, then $L \leq x \leq U$. If $y=0$, then $L \cdot 0 \leq x \leq U \cdot 0$, which means $0 \leq x \leq 0$, so $x=0$. This correctly models the disjoint range.

The Big M Method

The Big M method is a technique using a large constant $M$ to relax constraints based on binary variables, enabling the modeling of disjunctions and non-convex conditions.

Using Big M can lead to numerical instability and computational difficulties for solvers. It is generally advisable to avoid Big M if possible and seek alternative formulations.

The Big M method is a technique used to model disjunctive constraints and other non-convex conditions within linear and integer programming. It involves using a large constant, denoted as $M$, to relax constraints when certain binary variables are set to 0 or 1.

Introduction to Big M

The Big M method is a modeling trick that is used to handle logical conditions and disjunctions. It involves introducing a very large number $M$ (Big M) into the constraints.

Purpose and Drawbacks

The purpose of Big M is to make constraints conditionally active or inactive based on the value of binary variables. However, using Big M can have drawbacks. If $M$ is too large, it can lead to numerical instability and computational difficulties for solvers. If $M$ is too small it may incorrectly exclude feasible solutions. It is generally advisable to avoid Big M if possible and seek alternative formulations. Models using Big M are often weaker than formulations that avoid it.

Modeling Disjunctions

Union of Solution Sets

When we have a set of constraints and we want to ensure that at least one of them is satisfied, we are dealing with the union of feasible regions defined by each constraint. This union is generally non-convex.

Big M and Binary Variables

To model the OR condition, we introduce binary variables and the Big M technique. For example, to model "either $a_1x \leq b_1$ OR $a_2x \leq b_2$", we can use binary variables.

Constraints for OR of Inequalities

To model the condition that at least one of $k$ inequalities must hold, we use $k+1$ linear inequalities and introduce $k$ additional binary variables.

Suppose we want to model the condition that at least one of the following $k$ inequalities must hold: \[a_1x \leq b_1, \quad a_2x \leq b_2, \quad \dots, \quad a_kx \leq b_k\] We introduce binary variables $y_1, y_2, \dots, y_k$ and a sufficiently large number $M$. We then replace the original inequalities with:

\[\begin{aligned} a_1x &\leq b_1 + M y_1 \\ a_2x &\leq b_2 + M y_2 \\ &\vdots \\ a_kx &\leq b_k + M y_k \\ \sum_{i=1}^{k} y_i &\leq k - 1 \end{aligned}\] The constraint $\sum_{i=1}^{k} y_i \leq k - 1$ ensures that at least one $y_i$ must be 0. If $y_i = 0$, the $i$-th constraint becomes $a_ix \leq b_i$, which is enforced. If $y_i = 1$, the $i$-th constraint becomes $a_ix \leq b_i + M$, which is always satisfied if $M$ is large enough (making it loose). Thus, at least one of the original inequalities is enforced.

Modeling Exclusive OR

Big M can also be used to model exclusive OR conditions, where exactly one of several conditions must be true.

Example: Non-Preemptive Scheduling

Consider a non-preemptive scheduling problem where for any pair of jobs $i$ and $j$, either job $j$ must start after job $i$ finishes, or job $i$ must start after job $j$ finishes. This is an exclusive OR condition on the relative starting times of jobs.

Constraints for Exclusive OR of Inequalities

To model the condition that exactly one of two inequalities must hold, we use 3 linear inequalities and introduce 2 additional binary variables. For the non-preemptive scheduling example, we use 2 linear inequalities and 1 binary variable for each pair of jobs.

To model "exactly one of $a_1x \leq b_1$ OR $a_2x \leq b_2$", we can use binary variables $y_1, y_2$ and Big M:

\[\begin{aligned} a_1x &\leq b_1 + M y_1 \\ a_2x &\leq b_2 + M y_2 \\ y_1 + y_2 &= 1 \end{aligned}\] The constraint $y_1 + y_2 = 1$ ensures that exactly one of $y_1, y_2$ is 0 and the other is 1. If $y_1 = 0$, then $a_1x \leq b_1$ is enforced and $a_2x \leq b_2 + M$ becomes loose. If $y_2 = 0$, then $a_2x \leq b_2$ is enforced and $a_1x \leq b_1 + M$ becomes loose. Thus, exactly one of the inequalities $a_1x \leq b_1$ or $a_2x \leq b_2$ is satisfied.

For the non-preemptive scheduling example, let $x_i$ and $x_j$ be the start times of jobs $i$ and $j$, and $p_i$ and $p_j$ be their processing times. We want to model the condition that either job $j$ starts after job $i$ finishes, or job $i$ starts after job $j$ finishes. This can be expressed as: \[(x_j \geq x_i + p_i) \quad \oplus\quad (x_i \geq x_j + p_j)\] Using Big M and binary variable $y_{ij}$, we can model this as: \[\begin{aligned} x_j &\geq x_i + p_i - M y_{ij} \\ x_i &\geq x_j + p_j - M (1 - y_{ij}) \end{aligned}\] If $y_{ij} = 1$, the first constraint becomes $x_j \geq x_i + p_i - M$ (loose), and the second becomes $x_i \geq x_j + p_j$ (tight), meaning job $i$ starts after job $j$ finishes. If $y_{ij} = 0$, the first constraint becomes $x_j \geq x_i + p_i$ (tight), meaning job $j$ starts after job $i$ finishes, and the second becomes $x_i \geq x_j + p_j - M$ (loose).

Modeling the Maximum of Variables

Big M can be used to model the maximum of a set of variables.

Constraints for $z = \max(x_1, \dots, x_n)$

To model $z = \max(x_1, \dots, x_n)$, we use $2n+1$ linear inequalities and introduce $n$ additional binary variables. If we are minimizing $z$ in the objective function, we only need $n$ linear inequalities.

To model $z = \max(x_1, x_2, \dots, x_n)$, where $z, x_1, \dots, x_n$ are variables, we can use the following constraints:

\[\begin{aligned} z &\geq x_i \quad \text{for all } i = 1, 2, \dots, n \\ z &\leq x_i + M (1 - y_i) \quad \text{for all } i = 1, 2, \dots, n \\ \sum_{i=1}^{n} y_i &= 1 \\ y_i &\in \{0, 1\} \quad \text{for all } i = 1, 2, \dots, n \end{aligned}\] Here, $y_i$ are binary variables. The constraint $\sum_{i=1}^{n} y_i = 1$ ensures that exactly one $y_i$ is 1. If $y_j = 1$ for some $j$, then:

$z \geq x_i$ for all $i$ ensures $z \geq \max(x_1, \dots, x_n)$.
$z \leq x_j + M (1 - y_j) = x_j + M (1 - 1) = x_j$, so $z \leq x_j$.
For $i \neq j$, $z \leq x_i + M (1 - y_i) = x_i + M$ (loose).

Thus, $z \leq x_j$ and $z \geq x_j$ (from $z \geq x_j$) together imply $z = x_j$. Since $z \geq x_i$ for all $i$, $z = x_j = \max(x_1, \dots, x_n)$.

Using the Objective Function to Imply the Maximum

If we are minimizing $z$ in the objective function and we have the constraints $z \geq x_i$ for all $i$, then $z$ will automatically be forced to be the minimum value that is greater than or equal to all $x_i$s, which is $\max(x_1, \dots, x_n)$. In this case, we only need the constraints:

\[z \geq x_i \quad \text{for all } i = 1, 2, \dots, n\] and minimize $z$ in the objective function. This avoids the need for Big M and binary variables, leading to a more efficient formulation.

Modeling Absolute Value

To model $y = |x|$, we use 4 linear inequalities and introduce 1 additional binary variable. If we are minimizing $y$ in the objective function, we only need 2 linear inequalities.

Big M can be used to model the absolute value of a variable.

Constraints for $y = |x|$

To model $y = |x|$, where $y$ must be the absolute value of $x$, we can use the fact that $|x| = \max(x, -x)$. Using the Big M method for maximum, we can formulate it as:

\[\begin{aligned} y &\geq x \\ y &\geq -x \\ y &\leq x + M z \\ y &\leq -x + M (1 - z) \\ z &\in \{0, 1\} \end{aligned}\] Here, $z$ is a binary variable.

$y \geq x$ and $y \geq -x$ ensure $y \geq |x|$.
If $z = 0$, then $y \leq x$ and $y \leq -x + M$ (loose). So $y \leq x$. Combined with $y \geq x$, we get $y = x$. This corresponds to the case when $x \geq 0$, and $|x| = x$.
If $z = 1$, then $y \leq x + M$ (loose) and $y \leq -x$. So $y \leq -x$. Combined with $y \geq -x$, we get $y = -x$. This corresponds to the case when $x \leq 0$, and $|x| = -x$.

Thus, these constraints correctly model $y = |x|$.

Alternatively, if we are minimizing $y$ and we have $y \geq x$ and $y \geq -x$, then minimizing $y$ will naturally lead to $y = \max(x, -x) = |x|$. In this case, we only need:

\[\begin{aligned} y &\geq x \\ y &\geq -x \end{aligned}\] and minimize $y$ in the objective function.

Advanced Modeling Concepts

Beyond basic constraint formulations, advanced modeling concepts address model size, complexity, and the use of implicit models for very large-scale problems.

Model Size and Complexity

The size and complexity of a mathematical model are crucial factors in its solvability and practical applicability.

Instance Size vs. Model Size

Instance size refers to the dimensions of the real-world problem being modeled.

Model size refers to the number of variables and constraints in the mathematical formulation.

Instance size refers to the dimensions of the real-world problem being modeled (e.g., number of cities in TSP, number of jobs in scheduling). Model size refers to the number of variables and constraints in the mathematical formulation. Ideally, model size should be polynomially related to instance size for efficient solvability.

Polynomial Models

A model is polynomial if the number of variables and constraints grows polynomially with the instance size.

Polynomial models are generally desirable as they are more likely to be solvable efficiently.

A model is considered polynomial if the number of variables and constraints grows polynomially with the instance size. Most of the models we have discussed so far are polynomial models. Polynomial models are generally desirable as they are more likely to be solvable efficiently.

Exponential Models

A model is exponential if the number of variables or constraints grows exponentially with the instance size.

Exponential models can become computationally intractable for large instances if solved directly, but can be useful with oracles and decomposition methods.

A model is considered exponential if the number of variables or constraints grows exponentially with the instance size. Exponential models can become computationally intractable for large instances if solved directly. However, they can be useful when combined with techniques like oracles and decomposition methods.

Models with Exponential Constraints

Models with an exponential number of constraints might be necessary to accurately represent certain problems, especially those involving combinatorial structures.

Example: Cycles in a Graph

Consider a problem where we need to impose a constraint for every cycle in a graph. For example, in network design, we might want to avoid short cycles to ensure network robustness. The number of cycles in a dense graph can be exponential in the number of nodes. If we need to formulate a constraint for each cycle, the total number of constraints becomes exponential.

Models with Exponential Variables

Similarly, models might require an exponential number of variables to represent all possible solutions or configurations.

Example: Paths in a Graph

In path-based formulations of network flow problems, we might define a variable for every possible path between a source and a destination. The number of paths can be exponential in the size of the graph. For instance, if we want to select a set of paths in a graph, and we have a variable for each path indicating if it is selected, the number of variables can be exponential.

Implicit Models and Oracles

To handle exponential models, we often use implicit formulations and oracles. Instead of explicitly listing all constraints or variables, we work with a subset and use oracles to identify violated constraints or promising variables.

Oracles for Exponential Constraints

An oracle for exponential constraints is an algorithm that, given a solution, can efficiently determine if any of the exponentially many constraints are violated.

An oracle for exponential constraints is an algorithm that, given a solution, can efficiently determine if any of the exponentially many constraints are violated. If there are violated constraints, the oracle should return at least one. If no constraints are violated, it confirms the feasibility of the solution with respect to all constraints. This is used in techniques like cutting plane methods and branch and cut.

Initialize a model with a subset of constraints $C'$. Solve the model with $C'$ to obtain a solution $x^*$. Call the oracle with $x^*$ and $C'$. Add $c$ to $C'$. Resolve the model with the updated $C'$ to obtain a new solution $x^*$. $x^*$ (optimal solution).

The efficiency of this approach depends on the oracle’s ability to find a violated constraint in polynomial time, despite the exponential number of potential constraints. Grotschel, Lovasz, and Schrijver proved that if the oracle runs in polynomial time, the entire process can also be completed in polynomial time.

Oracles for Exponential Variables

An oracle for exponential variables, also known as a pricing oracle, identifies if there are any variables with negative reduced cost that could improve the current solution.

An oracle for exponential variables, also known as a pricing oracle, is used in column generation techniques. Given a dual solution, the pricing oracle identifies if there are any variables with negative reduced cost that could improve the current solution. If such variables exist, the oracle returns one or more of them to be added to the model.

Initialize a model with a subset of variables. Solve the model to obtain a solution $x^*$ and dual solution $\pi$. Call the pricing oracle with $\pi$. Add $x_j$ to the model. Resolve the model with the updated set of variables to obtain a new solution $x^*$ and dual solution $\pi$. $x^*$ (optimal solution).

Similar to the constraint oracle, the efficiency of this approach depends on the pricing oracle’s ability to find a variable with negative reduced cost in polynomial time.

Branch and Cut

Branch and cut is a method for solving integer linear programs that combines branch and bound with cutting plane methods.

Branch and cut is a method for solving integer linear programs that combines branch and bound with cutting plane methods. It is particularly effective for problems with a large number of constraints. In branch and cut, cutting planes (violated constraints identified by oracles) are added to tighten the linear programming relaxation at each node of the branch and bound tree.

Branch and Price

Branch and price is a method for solving integer linear programs that combines branch and bound with column generation.

Branch and price is a method for solving integer linear programs that combines branch and bound with column generation. It is effective for problems with a large number of variables. In branch and price, new variables (identified by pricing oracles) are added dynamically to the linear programming relaxation at each node of the branch and bound tree. Sometimes, for very complex problems, branch and cut and price is used, combining both constraint and variable generation techniques.

Conclusion

This lecture provided a comprehensive overview of constraint modeling in linear and integer programming. We covered various types of variables, basic and advanced constraint formulations, and techniques for handling complex logical conditions and non-convexities. Key takeaways include:

Linear inequalities are fundamental for formulating constraints.
Binary variables are essential for modeling logical conditions and discrete decisions.
Logical operations (OR, AND, NOT, XOR, Implication) can be translated into linear inequalities.
The Big M method is a useful trick for modeling disjunctions and non-convex regions, but should be used cautiously due to potential numerical issues.
Advanced modeling concepts like exponential models and oracles are necessary for solving very large-scale and complex problems.
Techniques like branch and cut and branch and price are used to solve models with a large number of constraints or variables, respectively, using oracles to manage complexity.

Further study in advanced optimization courses will delve deeper into oracles, cutting plane methods, column generation, and their applications in solving complex optimization problems. Understanding these modeling techniques is crucial for effectively applying linear and integer programming to real-world problems in various domains.

Follow-up Questions and Topics for Next Lecture:

Explore specific examples of problems where exponential models and oracles are effectively used (e.g., cutting stock, vehicle routing).
Investigate in more detail the algorithms for implementing oracles for constraint and variable generation.
Discuss the numerical stability issues associated with the Big M method and alternative formulations to avoid its use.
Introduce specific software and solvers for linear and integer programming and how to implement these modeling techniques in practice.

Important Remarks

Always aim for polynomial models if possible to ensure computational efficiency.
Use Big M method judiciously and consider alternative formulations when possible.
Oracles and implicit models are powerful tools for handling exponential complexity, but require careful design and implementation.
Understanding the logical structure of the problem is crucial for effective constraint modeling.

--- title: "Lecture Notes on Linear and Integer Programming: Constraints and Modeling" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture delves into the crucial aspect of formulating constraints in linear and integer programming models. We will explore various types of variables and how to represent different kinds of constraints, from basic linear inequalities to more complex logical conditions. The focus will be on transforming real-world problems into mathematical models suitable for optimization, emphasizing the use of binary variables to model logical operations and piecewise linear functions. We will also discuss advanced techniques like the Big M method for handling disjunctions and modeling non-convex feasible regions, and finally touch upon the concepts of model size, complexity, and implicit models. # Variables and Constraints ## Types of Variables In mathematical programming, selecting the right types of variables is fundamental to accurately model real-world problems. We primarily deal with two types of variables: numerical and binary. ### Numerical Variables ::: tcolorbox Numerical variables, also known as continuous variables, can take any real value within a defined range. ::: Numerical variables are used to represent quantities that can be measured on a continuous scale, such as production levels, amounts of resources, or time. ### Binary Variables ::: tcolorbox Binary variables, also known as 0-1 variables, can only take two values: 0 or 1. ::: They are essential for modeling yes/no decisions, logical conditions, and discrete choices. In the context of logic, 1 is often associated with 'true' and 0 with 'false'. ## Linear Constraints ::: tcolorbox A linear constraint is a restriction on variables expressed as a linear inequality or equality. ::: Constraints are restrictions or conditions that limit the possible values of the variables in a model. In linear programming, these constraints are linear inequalities or equalities. A general form of a linear constraint is given by: $$a_1x_1 + a_2x_2 + \dots + a_nx_n \geq B \quad \text{or} \quad a_1x_1 + a_2x_2 + \dots + a_nx_n \leq B$$ where $x_1, x_2, \dots, x_n$ are variables, and $a_1, a_2, \dots, a_n, B$ are constants. Linear equations are also valid constraints in linear programming, and importantly, a linear equation can be represented by two linear inequalities. For example, $ax = b$ is equivalent to $ax \geq b$ and $ax \leq b$. Thus, linear inequalities are the fundamental building blocks of constraints in linear programming. ## Piecewise Linear Constraints ::: tcolorbox A piecewise linear constraint involves functions that are linear in segments. ::: Piecewise linear constraints involve functions that are linear in segments. These can model situations where costs or values change at different thresholds. ### Linearization using Binary Variables Piecewise linear constraints can be linearized and incorporated into linear programming models by introducing binary variables. This technique allows us to handle non-linearities that arise from piecewise linear functions within the framework of linear programming. The exact method for linearization depends on the specific form of the piecewise linear function, and often involves introducing binary variables to select which linear segment is active. (Detail missing: teacher explanation unclear on specific linearization methods, further examples would be beneficial). # Linear Inequalities ::: tcolorbox A linear inequality is a constraint of the form $a_1x_1 + a_2x_2 + \dots + a_nx_n \geq B$ or $a_1x_1 + a_2x_2 + \dots + a_nx_n \leq B$. ::: Linear inequalities are the cornerstone of constraints in linear programming and integer programming. They define the feasible region within which the optimal solution must lie. ## Basic Forms Linear inequalities come in two basic forms, and equations can be represented using a combination of these. ### Greater Than or Equal To ($\geq$) The \"greater than or equal to\" inequality, denoted as $\geq$, specifies a minimum requirement or lower bound. It ensures that a linear combination of variables is at least a certain value. ### Less Than or Equal To ($\leq$) The \"less than or equal to\" inequality, denoted as $\leq$, specifies a maximum limit or upper bound. It ensures that a linear combination of variables does not exceed a certain value. ### Representing Linear Equations with Inequalities A linear equation $LHS = RHS$ can be represented by two linear inequalities: $LHS \geq RHS$ and $LHS \leq RHS$. This shows that inequalities are sufficient to express both inequality and equality constraints in linear programming. ## Coefficients and Constants In a linear inequality, coefficients (the $a_i$s) and constants (like $B$) are real numbers. These values are parameters of the problem and are fixed. They define the slope and intercept of the hyperplanes that bound the feasible region. ## Non-Negativity Constraints ::: tcolorbox A non-negativity constraint is a linear inequality of the form $x_i \geq 0$. ::: Non-negativity constraints are a common type of linear inequality, often written as $x_i \geq 0$. They restrict variables to be non-negative, which is natural in many real-world applications where variables represent physical quantities that cannot be negative (e.g., production quantity, amount of resource). These constraints are indeed a special case of the general linear inequality form, where for $x_1 \geq 0$, we can write it as $1 \cdot x_1 + 0 \cdot x_2 + \dots + 0 \cdot x_n \geq 0$. ## Interpretation of Inequalities Linear inequalities can be interpreted in various ways depending on the context of the problem. ### Guaranteeing Minimum Levels (using $\geq$) Inequalities of the form $\sum_{i} a_ix_i \geq B$ are often used to guarantee a minimum level of some requirement. This could represent ensuring a minimum production quantity, meeting dietary requirements, or maintaining a certain service level. ### Example: Dietary Requirements Consider formulating a dietary plan to meet a minimum sugar intake. Let $x_1$ be the number of apples, $x_2$ be the amount of bread (in hectograms), and $x_3$ be the amount of peas (in hectograms) consumed daily. Suppose an apple contains 19g of sugar, 100g of bread contains 5g of sugar, and 100g of peas contains 6g of sugar. If the minimum daily sugar requirement is 30g, the constraint can be written as: $$19x_1 + 5x_2 + 6x_3 \geq 30$$ This inequality ensures that the total sugar intake from apples, bread, and peas is at least 30g. Additional constraints, such as an upper limit on sugar intake, could also be added using $\leq$ inequalities. ## Variable Bounds ::: tcolorbox Variable bounds are linear inequalities that define the permissible range for individual variables, such as $l_i \leq x_i \leq u_i$. ::: Variable bounds are simple linear inequalities that define the range within which a variable must lie. ### Lower and Upper Bounds For a variable $x_i$, we can set a lower bound $l_i$ and an upper bound $u_i$ such that $l_i \leq x_i \leq u_i$. This is equivalent to two separate inequalities: $x_i \geq l_i$ and $x_i \leq u_i$. For instance, if we need to decide the number of pencils $x_i$ to purchase, and we must buy at least 20 but no more than 50, we would have $20 \leq x_i \leq 50$. ## Forcing Relationships Between Variables Linear inequalities are powerful tools for modeling logical relationships and dependencies between variables, especially when binary variables are involved. ### Logical Implications Linear inequalities can enforce logical implications between variables. For example, to model \"if condition A is true, then condition B must be true,\" we can use inequalities involving binary variables representing the truth values of conditions A and B. ### Boolean Conditions Boolean conditions, such as AND, OR, NOT, XOR, and implications, can be translated into linear inequalities, particularly when working with binary variables. This allows us to integrate logical constraints into linear and integer programming models. ## Loose vs. Non-Trivial Constraints When formulating constraints, it's important to understand whether a constraint is actually restricting the feasible region or if it is redundant. ### Definition of Loose Constraints ::: tcolorbox A constraint is considered loose if it is always satisfied whenever all other constraints are met. ::: A constraint is considered *loose* or *redundant* for a given assignment of variables if it is always satisfied by any feasible solution that meets all other constraints, especially around a specific variable assignment. Adding a loose constraint does not reduce the feasible region. ### Definition of Non-Trivial (Tight) Constraints ::: tcolorbox A constraint is considered non-trivial (tight) if it actively limits the feasible region. ::: A constraint is *non-trivial* or *tight* (or *binding*) for a given assignment of variables if it effectively restricts the feasible region. For certain variable assignments, a tight constraint can become critical in determining the feasibility of a solution. Adding a tight constraint can reduce the feasible region. ### Conditional Tightness Constraints can be conditionally tight, meaning they are loose under certain conditions (assignments of some variables) and tight under others. This property is particularly useful for modeling logical implications and conditional decisions. We aim to design constraints that are loose in most cases but become tight to enforce specific relationships when certain conditions are met. ## Examples Let's look at some examples to illustrate the concepts of loose and tight constraints. ### Example 1: $z \leq x + y$ Consider the constraint $z \leq x + y$, where $x, y, z$ are binary variables. This constraint is *loose* for all combinations of $(x, y)$ except when $x = 0$ and $y = 0$. - If $x=1$ or $y=1$, then $x+y \geq 1$, so $z \leq x+y$ becomes $z \leq 1$ or $z \leq 2$, which is always true for a binary variable $z \in \{0, 1\}$. - If $x=0$ and $y=0$, then $x+y = 0$, so $z \leq x+y$ becomes $z \leq 0$. Since $z$ is binary and non-negative, this forces $z = 0$. Logically, this constraint can be interpreted as: if $(x \lor y)$ is false (i.e., both $x$ and $y$ are false), then $z$ must be false. In Boolean logic terms: $(\neg x \land\neg y) \implies \neg z$. ### Example 2: $x \leq 20 - 15y$ Consider the constraint $x \leq 20 - 15y$, where $x$ is a real variable with an existing upper bound $x \leq 10$, and $y$ is a binary variable. - If $y = 0$, the constraint becomes $x \leq 20$. Since we already have $x \leq 10$, the constraint $x \leq 20$ is *loose* and redundant. - If $y = 1$, the constraint becomes $x \leq 20 - 15 = 5$. In this case, $x \leq 5$ is a *tight* constraint, which is more restrictive than the original bound $x \leq 10$. This constraint models a situation where the upper bound on $x$ depends on the value of the binary variable $y$. If $y$ is true (1), the bound on $x$ is tightened to 5; if $y$ is false (0), the bound remains effectively at 10 (considering the pre-existing constraint). We could also rewrite the constraint as $x \leq 10 - 5y$ to directly see that when $y=0$, $x \leq 10$, and when $y=1$, $x \leq 5$. # Logical Operations with Constraints Linear inequalities can be used to model various logical operations, which is crucial for formulating complex decision-making problems within linear and integer programming. ## Logical OR ::: tcolorbox The logical OR operation ($\lor$) is true if at least one of the operands is true. ::: ### Ensuring at Least One Variable is True To ensure that at least one of the binary variables $x_1, x_2, \dots, x_n$ is true (i.e., at least one is equal to 1), we can use the following constraint: $$x_1 + x_2 + \dots + x_n \geq 1$$ This inequality forces the sum of the variables to be at least 1, which means at least one variable must be 1. ### Covering Constraints ::: tcolorbox A covering constraint is of the form $\sum_{i} x_i \geq 1$, ensuring at least one variable is true. ::: A constraint of the form $\sum_{i} x_i \geq 1$ is also known as a *covering constraint*, as it ensures that at least one variable \"covers\" the condition of being true. ## Logical OR as a Variable Sometimes, we need a binary variable $z$ to represent the logical OR of several other binary variables $x_1, x_2, \dots, x_n$. We want $z$ to be 1 if $x_1 \lor x_2 \lor\dots \lor x_n$ is true, and 0 otherwise. ### Constraints for $z = x_1 \lor x_2 \lor\dots \lor x_n$ ::: tcolorbox To model $z = x_1 \lor x_2 \lor\dots \lor x_n$, we use $n+1$ linear inequalities. ::: To model $z = x_1 \lor x_2 \lor\dots \lor x_n$, we can use the following set of constraints: $$\begin{aligned} z &\leq x_1 + x_2 + \dots + x_n \\ z &\geq x_i \quad \text{for all } i = 1, 2, \dots, n \end{aligned}$$ - The constraint $z \leq x_1 + x_2 + \dots + x_n$ ensures that if all $x_i$s are 0, then $z$ must be 0. If at least one $x_i$ is 1, this constraint becomes loose (since $z \leq \sum x_i$ will be $z \leq 1$ or greater, which is always true for binary $z$). - The constraints $z \geq x_i$ for all $i$ ensure that if any $x_i$ is 1, then $z$ must also be 1. If all $x_i$s are 0, these constraints become $z \geq 0$, which is naturally satisfied for a binary variable. In total, we use $n+1$ linear inequalities to model the OR operation as a variable. ## Logical XOR ::: tcolorbox The logical XOR operation ($\oplus$) is true if exactly one of the operands is true. ::: ### Constraints for $z = x \oplus y$ ::: tcolorbox To model $z = x \oplus y$, we can use 4 linear inequalities or 1 equation with 1 additional binary variable. ::: To model $z = x \oplus y$, where $z, x, y$ are binary variables, we can use the following set of inequalities: $$\begin{aligned} z &\leq x + y \\ z &\leq 2 - x - y \\ z &\geq x - y \\ z &\geq y - x \end{aligned}$$ Let's analyze these constraints: - $z \leq x + y$: If $x=0$ and $y=0$, then $z \leq 0$, forcing $z=0$. - $z \leq 2 - x - y$: If $x=1$ and $y=1$, then $z \leq 2 - 1 - 1 = 0$, forcing $z=0$. - $z \geq x - y$ and $z \geq y - x$: These two together ensure that if exactly one of $x$ or $y$ is 1, then $z \geq 1$, forcing $z=1$. For instance, if $x=1, y=0$, $z \geq 1-0=1$ and $z \geq 0-1=-1$ (loose). If $x=0, y=1$, $z \geq 0-1=-1$ (loose) and $z \geq 1-0=1$. These four inequalities together correctly define $z = x \oplus y$. ### Alternative Formulation with an Additional Variable Another way to model $z = x \oplus y$ is using a single equation but with an additional binary variable $w$: $$z = x + y - 2w$$ where $w$ is a binary variable. This formulation ensures that $z$ has the same parity as $x + y$. - If $x+y = 0$ or $x+y = 2$ (both 0 or both 1), then $x+y$ is even, and to make $z$ binary and have the same parity, $z$ must be 0. - If $x+y = 1$ (one is 0 and the other is 1), then $x+y$ is odd, and to make $z$ binary and have the same parity, $z$ must be 1. ## Logical XOR as a Constraint Sometimes, we need to impose a constraint that the XOR of two or more variables must be true. ### Ensuring Exactly One Variable is True ::: tcolorbox To ensure exactly one of $x_1, x_2, \dots, x_n$ is true, we use 1 linear equation. ::: To ensure that exactly one of the binary variables $x_1, x_2, \dots, x_n$ is true, we use the constraint: $$x_1 + x_2 + \dots + x_n = 1$$ This equation forces the sum of the variables to be exactly 1, meaning precisely one variable must be 1, and all others must be 0. ### Partitioning/Selection Constraints ::: tcolorbox A partitioning/selection constraint is of the form $\sum_{i} x_i = 1$, ensuring exactly one variable is true. ::: Constraints of the form $\sum_{i} x_i = 1$ are known as *partitioning* or *selection constraints*. They are used when we need to select exactly one option out of several mutually exclusive choices. ## Assignment Constraints Assignment constraints are a specific application of selection constraints, particularly useful in problems involving assigning items to categories or tasks. ### Permutation Matrices ::: tcolorbox A permutation matrix is a square matrix where each row and each column has exactly one entry equal to 1, and all other entries are 0. ::: ::: tcolorbox To ensure a matrix is a permutation matrix, we use $2N$ linear equations for $N^2$ variables. ::: Consider a set of binary variables $x_{ij}$ where $i, j \in \{1, 2, \dots, N\}$. The constraints: $$\begin{aligned} \sum_{j=1}^{N} x_{ij} &= 1 \quad \text{for all } i = 1, 2, \dots, N \\ \sum_{i=1}^{N} x_{ij} &= 1 \quad \text{for all } j = 1, 2, \dots, N \end{aligned}$$ These constraints together ensure that the matrix $X = (x_{ij})$ is a permutation matrix. The first set of constraints ensures that for each row $i$, exactly one $x_{ij}$ is 1. The second set ensures that for each column $j$, exactly one $x_{ij}$ is 1. This structure is fundamental in assignment problems and problems involving permutations, such as the Traveling Salesperson Problem (TSP). In TSP, these constraints can be part of the formulation to ensure that each city is visited exactly once and left exactly once in a tour. ## Logical AND ::: tcolorbox The logical AND operation ($\land$) is true if and only if all operands are true. ::: ### Constraints for $z = x \land y$ ::: tcolorbox To model $z = x \land y$, we use 3 linear inequalities. To model $z = x_1 \land x_2 \land\dots \land x_n$, we use $n+1$ linear inequalities. ::: To model $z = x \land y$, where $z, x, y$ are binary variables, we can use the following set of inequalities: $$\begin{aligned} z &\leq x \\ z &\leq y \\ z &\geq x + y - 1 \end{aligned}$$ - $z \leq x$ and $z \leq y$: These ensure that if either $x=0$ or $y=0$, then $z$ must be 0. - $z \geq x + y - 1$: If $x=1$ and $y=1$, then $z \geq 1 + 1 - 1 = 1$, forcing $z=1$. If either $x$ or $y$ is 0, say $x=0$, then $z \geq 0 + y - 1 = y - 1$. Since $y \in \{0, 1\}$, $y-1$ is either -1 or 0, so $z \geq y-1$ becomes a loose constraint ($z \geq -1$ or $z \geq 0$, both are always true for binary $z$ as long as $z \geq 0$). These three inequalities correctly define $z = x \land y$. ### Constraints for $z = x_1 \land x_2 \land\dots \land x_n$ To generalize for $n$ variables, $z = x_1 \land x_2 \land\dots \land x_n$, we can use: $$\begin{aligned} z &\leq x_i \quad \text{for all } i = 1, 2, \dots, n \\ z &\geq \sum_{i=1}^{n} x_i - (n - 1) \end{aligned}$$ - $z \leq x_i$ for all $i$: Ensures $z=0$ if any $x_i=0$. - $z \geq \sum_{i=1}^{n} x_i - (n - 1)$: If all $x_i = 1$, then $z \geq n - (n - 1) = 1$, forcing $z=1$. If at least one $x_i = 0$, then $\sum_{i=1}^{n} x_i \leq n-1$, so $\sum_{i=1}^{n} x_i - (n - 1) \leq 0$, and $z \geq \sum_{i=1}^{n} x_i - (n - 1)$ becomes $z \geq 0$ or $z \geq \text{negative value}$, which is loose. ## Logical NOT ::: tcolorbox The logical NOT operation ($\neg$) is true if the operand is false, and false if the operand is true. ::: ### Constraints for $y = \neg x$ ::: tcolorbox To model $y = \neg x$, we use 1 linear equation. ::: To model $y = \neg x$, where $x, y$ are binary variables, we can simply use the equation: $$y = 1 - x$$ If $x=1$, $y=0$; if $x=0$, $y=1$. This equation directly represents the NOT operation. In practice, if we need $\neg x$, we can often directly use $1-x$ in linear expressions instead of introducing a new variable $y$. ## Logical Implication ::: tcolorbox The logical implication ($x \implies y$) is true if whenever $x$ is true, $y$ must also be true. ::: ### Constraints for $x \implies y$ ::: tcolorbox To model $x \implies y$, we use 1 linear inequality. ::: To model $x \implies y$, where $x, y$ are binary variables, we can use the inequality: $$y \geq x \quad \text{or equivalently } \quad y - x \geq 0$$ If $x=1$, then $y \geq 1$, forcing $y=1$. If $x=0$, then $y \geq 0$, which is always true for a binary variable, so $y$ can be either 0 or 1. This accurately models the implication. ## Complex Logical Conditions More complex logical conditions can be modeled by combining the basic logical operations we've discussed. ### Example: If $x$ then $y \implies z$, else $y$ or $z$ are false Consider the condition: \"If $x$ is true, then ($y$ implies $z$), else ($y$ is false OR $z$ is false)\". In logical notation: $(x \implies(y \implies z)) \land(\neg x \implies(\neg y \lor\neg z))$. We can analyze the truth table for this condition to derive constraints. Analyzing the condition: - If $x = \text{true}$ (1), then $y \implies z$ must be true. $y \implies z$ is false only when $y = \text{true}$ and $z = \text{false}$ (1 and 0). So, if $x=1$, we must not have $y=1$ and $z=0$. - If $x = \text{false}$ (0), then $\neg y \lor\neg z$ must be true. This means it's not allowed to have both $y = \text{true}$ and $z = \text{true}$ (1 and 1). So, if $x=0$, we must not have $y=1$ and $z=1$. Forbidden configurations are $(x, y, z) = (1, 1, 0)$ and $(x, y, z) = (0, 1, 1)$. ### Prohibiting Specific Bit Configurations ::: tcolorbox To prohibit a specific bit configuration of $n$ binary variables, we use 1 linear inequality. ::: To prohibit specific bit configurations, we can use linear inequalities. For $n$ binary variables $x_1, x_2, \dots, x_n$, to forbid a configuration $(b_1, b_2, \dots, b_n)$, we can use the constraint: $$\sum_{i: b_i=1} x_i + \sum_{i: b_i=0} (1 - x_i) \leq n - 1$$ For configuration $(1, 1, 0)$, i.e., $(x, y, z) = (1, 1, 0)$, we have $n=3$. Bits at positions 1 and 2 are 1, bit at position 3 is 0. So, the constraint is: $x + y + (1 - z) \leq 3 - 1 = 2$, which simplifies to $x + y - z \leq 1$. For configuration $(0, 1, 1)$, i.e., $(x, y, z) = (0, 1, 1)$, we have $n=3$. Bit at position 1 is 0, bits at positions 2 and 3 are 1. So, the constraint is: $(1 - x) + y + z \leq 3 - 1 = 2$, which simplifies to $-x + y + z \leq 1$. Thus, the constraints to enforce the complex logical condition are: $$\begin{aligned} x + y - z &\leq 1 \\ -x + y + z &\leq 1 \end{aligned}$$ ## Variable Ranges Constraints can also be used to define the permissible ranges for variables, which can be continuous or disjoint. ### Lower and Upper Bounds As discussed earlier, lower and upper bounds $l_i \leq x_i \leq u_i$ define a continuous range for variable $x_i$. ### Disjoint Ranges Sometimes, we need to model situations where a variable can take values from disjoint ranges. For example, a variable $x$ can be either 0 or in the range $[L, U]$, where $L > 0$. This creates a non-convex feasible region. #### Modeling with an Additional Binary Variable ::: tcolorbox To model disjoint ranges like $x=0$ or $L \leq x \leq U$, we use 3 linear inequalities and introduce 1 additional binary variable. ::: To model disjoint ranges like $x=0$ or $L \leq x \leq U$, we can introduce a binary variable $y \in \{0, 1\}$ and use the following constraints: $$\begin{aligned} x &\geq L \cdot y \\ x &\leq U \cdot y \\ x &\geq 0 \end{aligned}$$ If $y=1$, then$$\begin{aligned} x &\geq L \cdot y \\ x &\leq U \cdot y \\ x &\geq 0 \end{aligned}$$ If $y=1$, then $L \leq x \leq U$. If $y=0$, then $L \cdot 0 \leq x \leq U \cdot 0$, which means $0 \leq x \leq 0$, so $x=0$. This correctly models the disjoint range. # The Big M Method ::: tcolorbox The Big M method is a technique using a large constant $M$ to relax constraints based on binary variables, enabling the modeling of disjunctions and non-convex conditions. ::: ::: tcolorbox Using Big M can lead to numerical instability and computational difficulties for solvers. It is generally advisable to avoid Big M if possible and seek alternative formulations. ::: The Big M method is a technique used to model disjunctive constraints and other non-convex conditions within linear and integer programming. It involves using a large constant, denoted as $M$, to relax constraints when certain binary variables are set to 0 or 1. ## Introduction to Big M The Big M method is a modeling trick that is used to handle logical conditions and disjunctions. It involves introducing a very large number $M$ (Big M) into the constraints. ### Purpose and Drawbacks The purpose of Big M is to make constraints conditionally active or inactive based on the value of binary variables. However, using Big M can have drawbacks. If $M$ is too large, it can lead to numerical instability and computational difficulties for solvers. If $M$ is too small it may incorrectly exclude feasible solutions. It is generally advisable to avoid Big M if possible and seek alternative formulations. Models using Big M are often weaker than formulations that avoid it. ## Modeling Disjunctions ### Union of Solution Sets When we have a set of constraints and we want to ensure that at least one of them is satisfied, we are dealing with the union of feasible regions defined by each constraint. This union is generally non-convex. ### Big M and Binary Variables To model the OR condition, we introduce binary variables and the Big M technique. For example, to model \"either $a_1x \leq b_1$ OR $a_2x \leq b_2$\", we can use binary variables. ### Constraints for OR of Inequalities ::: tcolorbox To model the condition that at least one of $k$ inequalities must hold, we use $k+1$ linear inequalities and introduce $k$ additional binary variables. ::: Suppose we want to model the condition that at least one of the following $k$ inequalities must hold: $$a_1x \leq b_1, \quad a_2x \leq b_2, \quad \dots, \quad a_kx \leq b_k$$ We introduce binary variables $y_1, y_2, \dots, y_k$ and a sufficiently large number $M$. We then replace the original inequalities with: $$\begin{aligned} a_1x &\leq b_1 + M y_1 \\ a_2x &\leq b_2 + M y_2 \\ &\vdots \\ a_kx &\leq b_k + M y_k \\ \sum_{i=1}^{k} y_i &\leq k - 1 \end{aligned}$$ The constraint $\sum_{i=1}^{k} y_i \leq k - 1$ ensures that at least one $y_i$ must be 0. If $y_i = 0$, the $i$-th constraint becomes $a_ix \leq b_i$, which is enforced. If $y_i = 1$, the $i$-th constraint becomes $a_ix \leq b_i + M$, which is always satisfied if $M$ is large enough (making it loose). Thus, at least one of the original inequalities is enforced. ## Modeling Exclusive OR Big M can also be used to model exclusive OR conditions, where exactly one of several conditions must be true. ### Example: Non-Preemptive Scheduling Consider a non-preemptive scheduling problem where for any pair of jobs $i$ and $j$, either job $j$ must start after job $i$ finishes, or job $i$ must start after job $j$ finishes. This is an exclusive OR condition on the relative starting times of jobs. ### Constraints for Exclusive OR of Inequalities ::: tcolorbox To model the condition that exactly one of two inequalities must hold, we use 3 linear inequalities and introduce 2 additional binary variables. For the non-preemptive scheduling example, we use 2 linear inequalities and 1 binary variable for each pair of jobs. ::: To model \"exactly one of $a_1x \leq b_1$ OR $a_2x \leq b_2$\", we can use binary variables $y_1, y_2$ and Big M: $$\begin{aligned} a_1x &\leq b_1 + M y_1 \\ a_2x &\leq b_2 + M y_2 \\ y_1 + y_2 &= 1 \end{aligned}$$ The constraint $y_1 + y_2 = 1$ ensures that exactly one of $y_1, y_2$ is 0 and the other is 1. If $y_1 = 0$, then $a_1x \leq b_1$ is enforced and $a_2x \leq b_2 + M$ becomes loose. If $y_2 = 0$, then $a_2x \leq b_2$ is enforced and $a_1x \leq b_1 + M$ becomes loose. Thus, exactly one of the inequalities $a_1x \leq b_1$ or $a_2x \leq b_2$ is satisfied. For the non-preemptive scheduling example, let $x_i$ and $x_j$ be the start times of jobs $i$ and $j$, and $p_i$ and $p_j$ be their processing times. We want to model the condition that either job $j$ starts after job $i$ finishes, or job $i$ starts after job $j$ finishes. This can be expressed as: $$(x_j \geq x_i + p_i) \quad \oplus\quad (x_i \geq x_j + p_j)$$ Using Big M and binary variable $y_{ij}$, we can model this as: $$\begin{aligned} x_j &\geq x_i + p_i - M y_{ij} \\ x_i &\geq x_j + p_j - M (1 - y_{ij}) \end{aligned}$$ If $y_{ij} = 1$, the first constraint becomes $x_j \geq x_i + p_i - M$ (loose), and the second becomes $x_i \geq x_j + p_j$ (tight), meaning job $i$ starts after job $j$ finishes. If $y_{ij} = 0$, the first constraint becomes $x_j \geq x_i + p_i$ (tight), meaning job $j$ starts after job $i$ finishes, and the second becomes $x_i \geq x_j + p_j - M$ (loose). ## Modeling the Maximum of Variables Big M can be used to model the maximum of a set of variables. ### Constraints for $z = \max(x_1, \dots, x_n)$ ::: tcolorbox To model $z = \max(x_1, \dots, x_n)$, we use $2n+1$ linear inequalities and introduce $n$ additional binary variables. If we are minimizing $z$ in the objective function, we only need $n$ linear inequalities. ::: To model $z = \max(x_1, x_2, \dots, x_n)$, where $z, x_1, \dots, x_n$ are variables, we can use the following constraints: $$\begin{aligned} z &\geq x_i \quad \text{for all } i = 1, 2, \dots, n \\ z &\leq x_i + M (1 - y_i) \quad \text{for all } i = 1, 2, \dots, n \\ \sum_{i=1}^{n} y_i &= 1 \\ y_i &\in \{0, 1\} \quad \text{for all } i = 1, 2, \dots, n \end{aligned}$$ Here, $y_i$ are binary variables. The constraint $\sum_{i=1}^{n} y_i = 1$ ensures that exactly one $y_i$ is 1. If $y_j = 1$ for some $j$, then: - $z \geq x_i$ for all $i$ ensures $z \geq \max(x_1, \dots, x_n)$. - $z \leq x_j + M (1 - y_j) = x_j + M (1 - 1) = x_j$, so $z \leq x_j$. - For $i \neq j$, $z \leq x_i + M (1 - y_i) = x_i + M$ (loose). Thus, $z \leq x_j$ and $z \geq x_j$ (from $z \geq x_j$) together imply $z = x_j$. Since $z \geq x_i$ for all $i$, $z = x_j = \max(x_1, \dots, x_n)$. ### Using the Objective Function to Imply the Maximum If we are minimizing $z$ in the objective function and we have the constraints $z \geq x_i$ for all $i$, then $z$ will automatically be forced to be the minimum value that is greater than or equal to all $x_i$s, which is $\max(x_1, \dots, x_n)$. In this case, we only need the constraints: $$z \geq x_i \quad \text{for all } i = 1, 2, \dots, n$$ and minimize $z$ in the objective function. This avoids the need for Big M and binary variables, leading to a more efficient formulation. ## Modeling Absolute Value ::: tcolorbox To model $y = |x|$, we use 4 linear inequalities and introduce 1 additional binary variable. If we are minimizing $y$ in the objective function, we only need 2 linear inequalities. ::: Big M can be used to model the absolute value of a variable. ### Constraints for $y = |x|$ To model $y = |x|$, where $y$ must be the absolute value of $x$, we can use the fact that $|x| = \max(x, -x)$. Using the Big M method for maximum, we can formulate it as: $$\begin{aligned} y &\geq x \\ y &\geq -x \\ y &\leq x + M z \\ y &\leq -x + M (1 - z) \\ z &\in \{0, 1\} \end{aligned}$$ Here, $z$ is a binary variable. - $y \geq x$ and $y \geq -x$ ensure $y \geq |x|$. - If $z = 0$, then $y \leq x$ and $y \leq -x + M$ (loose). So $y \leq x$. Combined with $y \geq x$, we get $y = x$. This corresponds to the case when $x \geq 0$, and $|x| = x$. - If $z = 1$, then $y \leq x + M$ (loose) and $y \leq -x$. So $y \leq -x$. Combined with $y \geq -x$, we get $y = -x$. This corresponds to the case when $x \leq 0$, and $|x| = -x$. Thus, these constraints correctly model $y = |x|$. Alternatively, if we are minimizing $y$ and we have $y \geq x$ and $y \geq -x$, then minimizing $y$ will naturally lead to $y = \max(x, -x) = |x|$. In this case, we only need: $$\begin{aligned} y &\geq x \\ y &\geq -x \end{aligned}$$ and minimize $y$ in the objective function. # Advanced Modeling Concepts Beyond basic constraint formulations, advanced modeling concepts address model size, complexity, and the use of implicit models for very large-scale problems. ## Model Size and Complexity The size and complexity of a mathematical model are crucial factors in its solvability and practical applicability. ### Instance Size vs. Model Size ::: tcolorbox Instance size refers to the dimensions of the real-world problem being modeled. ::: ::: tcolorbox Model size refers to the number of variables and constraints in the mathematical formulation. ::: *Instance size* refers to the dimensions of the real-world problem being modeled (e.g., number of cities in TSP, number of jobs in scheduling). *Model size* refers to the number of variables and constraints in the mathematical formulation. Ideally, model size should be polynomially related to instance size for efficient solvability. ### Polynomial Models ::: tcolorbox A model is polynomial if the number of variables and constraints grows polynomially with the instance size. ::: ::: tcolorbox Polynomial models are generally desirable as they are more likely to be solvable efficiently. ::: A model is considered *polynomial* if the number of variables and constraints grows polynomially with the instance size. Most of the models we have discussed so far are polynomial models. Polynomial models are generally desirable as they are more likely to be solvable efficiently. ### Exponential Models ::: tcolorbox A model is exponential if the number of variables or constraints grows exponentially with the instance size. ::: ::: tcolorbox Exponential models can become computationally intractable for large instances if solved directly, but can be useful with oracles and decomposition methods. ::: A model is considered *exponential* if the number of variables or constraints grows exponentially with the instance size. Exponential models can become computationally intractable for large instances if solved directly. However, they can be useful when combined with techniques like oracles and decomposition methods. ## Models with Exponential Constraints Models with an exponential number of constraints might be necessary to accurately represent certain problems, especially those involving combinatorial structures. ### Example: Cycles in a Graph Consider a problem where we need to impose a constraint for every cycle in a graph. For example, in network design, we might want to avoid short cycles to ensure network robustness. The number of cycles in a dense graph can be exponential in the number of nodes. If we need to formulate a constraint for each cycle, the total number of constraints becomes exponential. ## Models with Exponential Variables Similarly, models might require an exponential number of variables to represent all possible solutions or configurations. ### Example: Paths in a Graph In path-based formulations of network flow problems, we might define a variable for every possible path between a source and a destination. The number of paths can be exponential in the size of the graph. For instance, if we want to select a set of paths in a graph, and we have a variable for each path indicating if it is selected, the number of variables can be exponential. ## Implicit Models and Oracles To handle exponential models, we often use implicit formulations and oracles. Instead of explicitly listing all constraints or variables, we work with a subset and use oracles to identify violated constraints or promising variables. ### Oracles for Exponential Constraints ::: tcolorbox An oracle for exponential constraints is an algorithm that, given a solution, can efficiently determine if any of the exponentially many constraints are violated. ::: An *oracle* for exponential constraints is an algorithm that, given a solution, can efficiently determine if any of the exponentially many constraints are violated. If there are violated constraints, the oracle should return at least one. If no constraints are violated, it confirms the feasibility of the solution with respect to all constraints. This is used in techniques like *cutting plane methods* and *branch and cut*. :::: algorithm ::: algorithmic Initialize a model with a subset of constraints $C'$. Solve the model with $C'$ to obtain a solution $x^*$. Call the oracle with $x^*$ and $C'$. Add $c$ to $C'$. Resolve the model with the updated $C'$ to obtain a new solution $x^*$. $x^*$ (optimal solution). ::: :::: The efficiency of this approach depends on the oracle's ability to find a violated constraint in polynomial time, despite the exponential number of potential constraints. Grotschel, Lovasz, and Schrijver proved that if the oracle runs in polynomial time, the entire process can also be completed in polynomial time. ### Oracles for Exponential Variables ::: tcolorbox An oracle for exponential variables, also known as a pricing oracle, identifies if there are any variables with negative reduced cost that could improve the current solution. ::: An *oracle* for exponential variables, also known as a *pricing oracle*, is used in column generation techniques. Given a dual solution, the pricing oracle identifies if there are any variables with negative reduced cost that could improve the current solution. If such variables exist, the oracle returns one or more of them to be added to the model. :::: algorithm ::: algorithmic Initialize a model with a subset of variables. Solve the model to obtain a solution $x^*$ and dual solution $\pi$. Call the pricing oracle with $\pi$. Add $x_j$ to the model. Resolve the model with the updated set of variables to obtain a new solution $x^*$ and dual solution $\pi$. $x^*$ (optimal solution). ::: :::: Similar to the constraint oracle, the efficiency of this approach depends on the pricing oracle's ability to find a variable with negative reduced cost in polynomial time. ### Branch and Cut ::: tcolorbox Branch and cut is a method for solving integer linear programs that combines branch and bound with cutting plane methods. ::: *Branch and cut* is a method for solving integer linear programs that combines branch and bound with cutting plane methods. It is particularly effective for problems with a large number of constraints. In branch and cut, cutting planes (violated constraints identified by oracles) are added to tighten the linear programming relaxation at each node of the branch and bound tree. ### Branch and Price ::: tcolorbox Branch and price is a method for solving integer linear programs that combines branch and bound with column generation. ::: *Branch and price* is a method for solving integer linear programs that combines branch and bound with column generation. It is effective for problems with a large number of variables. In branch and price, new variables (identified by pricing oracles) are added dynamically to the linear programming relaxation at each node of the branch and bound tree. Sometimes, for very complex problems, *branch and cut and price* is used, combining both constraint and variable generation techniques. # Conclusion This lecture provided a comprehensive overview of constraint modeling in linear and integer programming. We covered various types of variables, basic and advanced constraint formulations, and techniques for handling complex logical conditions and non-convexities. Key takeaways include: - Linear inequalities are fundamental for formulating constraints. - Binary variables are essential for modeling logical conditions and discrete decisions. - Logical operations (OR, AND, NOT, XOR, Implication) can be translated into linear inequalities. - The Big M method is a useful trick for modeling disjunctions and non-convex regions, but should be used cautiously due to potential numerical issues. - Advanced modeling concepts like exponential models and oracles are necessary for solving very large-scale and complex problems. - Techniques like branch and cut and branch and price are used to solve models with a large number of constraints or variables, respectively, using oracles to manage complexity. Further study in advanced optimization courses will delve deeper into oracles, cutting plane methods, column generation, and their applications in solving complex optimization problems. Understanding these modeling techniques is crucial for effectively applying linear and integer programming to real-world problems in various domains. **Follow-up Questions and Topics for Next Lecture:** - Explore specific examples of problems where exponential models and oracles are effectively used (e.g., cutting stock, vehicle routing). - Investigate in more detail the algorithms for implementing oracles for constraint and variable generation. - Discuss the numerical stability issues associated with the Big M method and alternative formulations to avoid its use. - Introduce specific software and solvers for linear and integer programming and how to implement these modeling techniques in practice. ## Important Remarks {#important-remarks .unnumbered} - Always aim for polynomial models if possible to ensure computational efficiency. - Use Big M method judiciously and consider alternative formulations when possible. - Oracles and implicit models are powerful tools for handling exponential complexity, but require careful design and implementation. - Understanding the logical structure of the problem is crucial for effective constraint modeling.

Introduction

Variables and Constraints

Types of Variables

Numerical Variables

Binary Variables

Linear Constraints

Piecewise Linear Constraints

Linearization using Binary Variables

Linear Inequalities

Basic Forms

Greater Than or Equal To (\(\geq\))

Less Than or Equal To (\(\leq\))

Representing Linear Equations with Inequalities

Coefficients and Constants

Non-Negativity Constraints

Interpretation of Inequalities

Guaranteeing Minimum Levels (using \(\geq\))

Example: Dietary Requirements

Variable Bounds

Lower and Upper Bounds

Forcing Relationships Between Variables

Logical Implications

Boolean Conditions

Loose vs. Non-Trivial Constraints

Definition of Loose Constraints

Definition of Non-Trivial (Tight) Constraints

Conditional Tightness

Examples

Example 1: \(z \leq x + y\)

Example 2: \(x \leq 20 - 15y\)

Logical Operations with Constraints

Logical OR

Ensuring at Least One Variable is True

Covering Constraints

Logical OR as a Variable

Constraints for \(z = x_1 \lor x_2 \lor\dots \lor x_n\)

Logical XOR

Constraints for \(z = x \oplus y\)

Alternative Formulation with an Additional Variable

Logical XOR as a Constraint

Ensuring Exactly One Variable is True

Partitioning/Selection Constraints

Assignment Constraints

Permutation Matrices

Logical AND

Constraints for \(z = x \land y\)

Constraints for \(z = x_1 \land x_2 \land\dots \land x_n\)

Logical NOT

Constraints for \(y = \neg x\)

Logical Implication

Constraints for \(x \implies y\)

Complex Logical Conditions

Example: If \(x\) then \(y \implies z\), else \(y\) or \(z\) are false

Prohibiting Specific Bit Configurations

Variable Ranges

Lower and Upper Bounds

Disjoint Ranges

Modeling with an Additional Binary Variable

The Big M Method

Introduction to Big M

Purpose and Drawbacks

Modeling Disjunctions

Union of Solution Sets

Big M and Binary Variables

Constraints for OR of Inequalities

Modeling Exclusive OR

Example: Non-Preemptive Scheduling

Constraints for Exclusive OR of Inequalities

Modeling the Maximum of Variables

Constraints for \(z = \max(x_1, \dots, x_n)\)

Using the Objective Function to Imply the Maximum

Modeling Absolute Value

Constraints for \(y = |x|\)

Advanced Modeling Concepts

Model Size and Complexity

Instance Size vs. Model Size

Polynomial Models

Exponential Models

Models with Exponential Constraints

Example: Cycles in a Graph