1
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ The condition "a set of $k$ vectors in $R^n$ is linearly independent" is not a linear condition, so most likely no. Anyway, integer programming is more suitable for combinatorial problems. $\endgroup$ Commented Jan 11, 2023 at 9:17
  • 1
    $\begingroup$ Ok, thanks for the answer ! But i just put this property as an example. In the genreral case, where i have some property X that can be expressed as a linear condition, is there a way to find the maximal size of a set having this property using linear programming ? $\endgroup$ Commented Jan 11, 2023 at 10:38
  • 1
    $\begingroup$ This is a bit too vague to answer I think. $\endgroup$ Commented Jan 11, 2023 at 11:08
  • 1
    $\begingroup$ Ok i see ! I edited my initial post to make my question a bit less vague (i hope) $\endgroup$ Commented Jan 11, 2023 at 14:55
  • 2
    $\begingroup$ Not sure if this counts, but given a set of vectors in ${\Bbb R}^n$ and some $\theta \in {\Bbb R}$, you could find the maximum subset $S$ such that if ${\bf u}, {\bf v} \in S$, then the angle between ${\bf u}$ and ${\bf v}$ is at least $\theta$. (This is just a graph theory problem in disguise.) $\endgroup$ Commented Jan 11, 2023 at 15:20

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.