I just learnt the basics of linear and integer programming, i know that for a given property X, it is sometimes possible to rewrite the question "What is the maximal size of a set having property X ?" as a integer program.
For instance, in graph theory the problem of finding a maximal independent set of $G=(V,E)$ could be rewritten this way (with $|V|=n$): $$max \sum\limits_{i=1}^n c_i \quad \text{with} \quad \forall i, c_i \in \{0,1\} \quad \text{and} \quad \forall (uv) \in E, c_u+c_v \leq 1. $$
However this situation is a bit specific: we already know beforehand that the maximal size of such a set cannot be more than $n$ and more importantly the amount of subsets of $V$ is finite.
I'm wondering if this can be adapted to more general problems, particularly in linear algebra.
Let's take an example: pretend that i don't know the maximal size of a linearly independent set of vectors in $\mathbb{R}^n$. Let's say i only managed to prove that the size of such sets cannot exceed $n^2$.
Is there a way to rewrite the problem "What is the maximal size of a set of linearly independent vectors in $\mathbb{R^n}$ ?" as a linear or an integer program ? How should i do it ?
(It does not really matter if the number of variables/constraints is excessively large, i just want to understand how it would be done).
Thanks in advance for the answers/explanations !
EDIT: I'll try to make my question less vague:
I know that it is often possible to rewrite problems about determining the maximum size of sets satisfying a given property $X$ as integer programs.
The only examples i have in mind come from graph theory. \
Basically if $G=(V,E)$ and i'm looking for a subset of $V$, i will let x be a $0-1$ vector with
as many coordinates as the size of $V$. Then i will try to maximise the sum of the coordinates of $x$. This works because $V$ is a finite set so $x$ has a finite amount of coordinates $x_i$.
Now, in the case of linear algebra for instance, i will be looking for a maximal subset of $\mathbb{R}^n$ satisfying property $X$. Or maybe i'm doing
arithmetics and looking for the maximal size of a set of positive integers satisfying property $X$.
In both scenarios, even if i assume that the answer to my question is a finite number, i cannot use the same "trick" as for graphs:
the vector $x$ would need to have the same size as $\mathbb{R^n}$ (or $\mathbb{N}$) so it would have infinitely many coordinates.
Do you know any example of a problem of this kind ("Find the maximal size of a subset of S satisfying a given property X", where $S$ is infinite) which can
be rewritten as an integer/linear program anyway ? If so i would be eager to see one and i'm especially curious to see what the objective function and variables should look like.
If S is finite, fiding the subset H of S which has the greater cardinal subject to elements in S satisfying a property could be modeled as it follows,
\begin{equation} \begin{split} \max_{\alpha\in \mathbb{R}^{|S|}}&\ \ \sum_{i\in |S|}\alpha_{i} \\ \textrm{s.t.}&\ \ f(\alpha_{1},\dots,\alpha_{|S|})\leq0\\ &\ \ \alpha_{i}\in \{0,1\}. \end{split} \end{equation}
Where f represents the conditions that must be satisfied. In your example, $|S|=n$, $\alpha_{i}=c_{i}$, and $f_{i,j}(\alpha_{1},\dots,\alpha_{n})=\alpha_{i}+\alpha_{j}-1\leq 0$.
As it was noticed in the comments sections, this type of problems belongs to integer programming (becasue the variable $\alpha_{i}\in \mathbb{Z}$ ), which, in general, are difficult to resolve.