2
$\begingroup$

Problem

Given rectangular matrices $A$, $B$ and vectors $\vec{a}$, $\vec{b}$, how to check if there exists an $\vec{x}$ that satisfies the following conditions?

  1. $\vec{x} \succcurlyeq \vec{0}$ is true.
  2. $A\vec{x} \succcurlyeq \vec{a}$ is true.
  3. $B\vec{x} \succcurlyeq \vec{b}$ is false.

For vectors $\vec{u}$ and $\vec{v}$, $\vec{u} \succcurlyeq \vec{v}$ means:

  • The vectors have the same number of elements.
  • For all i, the ith elements of the vectors satisfy $u_i > v_i$.

I can't use $B\vec{x} \preccurlyeq \vec{b}$ because $\vec{x}$ only have to violate at least 1 inequalities among all inequalities represented by $B\vec{x} \succcurlyeq \vec{b}$.

Each problem has about 100 variables and 150 inequalities. I want to solve at least 10,000 problems per minute on a laptop. All of the problems share a large number of inequalities.


Ideas

Define two problems:

  • $P_{A}$ means $\vec{x} \succcurlyeq \vec{0}$ and $A\vec{x} \succcurlyeq \vec{a}$ are true.
  • $P_{B}$ means $\vec{x} \succcurlyeq \vec{0}$ and $B\vec{x} \succcurlyeq \vec{b}$ are true.

If I remember correctly, I think:

  • Vectors that satisfies $P_{A}$ are the convex combinations of the vertex set $V_{A}$.
    • The vectors in $V_A$ form a matrix $M_{A}$.
    • The convex combinations form a convex set $S_{A}$.
  • Vectors that satisfies $P_{B}$ are the convex combinations of the vertex set $V_{B}$.
    • The vectors in $V_B$ form a matrix $M_{B}$.
    • The convex combinations form a convex set $S_{B}$.
  • Intersection of two convex sets is convex.
  • Difference of two convex sets is not necessarily convex.

Idea 2

  • The problem is equivalent to showing if $S_{A}$ is not a subset of $S_{B}$.
  • I think the problem is also equivalent to showing if there exists a vertex $\vec{\alpha} \in V_A$ such that $\vec{\alpha}$ is not a convex combination of $V_B$. That means $M_{B}\vec{u} = \vec{\alpha}$ either has no solution or $\vec{u}\cdot\vec{1} \ne 1$.

I don't know how to find the vertexes. And there are potentially so many vertexes.

Idea 3

  • Start from an old problem without such a $\vec{x}$
  • By comparing the new $P_{B}$ and old $P_{B}$, we can identify the new cuts.
  • Invert the comparison in the new cuts. ($\ge$ to $\le$).
  • Check if each new inverted cut is compatible with the new $P_{A}$.
    • For each inverted new cut, add the inverted new cut to the new $P_A$. If simplex algorithm says the combined problem is feasible, the new inverted cut is compatible with the new $P_A$.
  • The new problem has such a $\vec{x}$ if and only if we find a new inverted cut that is incompatible with the new $P_{A}$.

That would be at most 60 runs of simplex per problem. The method caches the inequalities instead of the vertices.

I don't need the solution and only need to know if the new inverted cut is compatible with the existing cuts. Is there a faster way to get this?

$\endgroup$
2
$\begingroup$

I am assuming your notation means $u_i \ge v_i$ rather than $u_i > v_i$. Strict inequalities are somewhat problematic here.

First comment: Regardless of how you end up modeling this, I would be very surprised if you could solve 10,000 instances per minute on a laptop, even if consecutive instances have considerable commonality.

Second comment: For statement 3 to be false, there must be an index $i$ such that $B^{(i)} x < b_i$ (where $B^{(i)}$ denotes the $i$-th row of $B$. In practice, strict inequalities likely cannot be handled (especially if you end up solving an optimization problem), so you will almost certainly have to introduce a tolerance $\epsilon > 0$ and change statement 3 to $B^{(i)}x \le b_i - \epsilon$ for some $i$.

Third comment: Unless you know that the feasible regions of $P_A$ and $P_B$ are bounded, the correct statement is that a point in either one is the sum of a convex combination of vertices and nonnegative combination of rays (extreme directions).

Fourth comment: Identifying all vertices (and rays) of a polyhedron can be computationally expensive ... plus, for condition 3, you would need to show that the chosen $x$ cannot be expressed in terms of vertices and rays, which would be tricky.

Last comment: You can model this as a mixed integer linear program (though I'd be even more certain that 10K solutions per minute would be off the table). Introduce a binary variable $y_i$ with the same dimension as the number of rows in $B$. The feasible region for your problem is defined by $$x\ge 0$$ $$Ax\ge a$$ $$B^{(i)}x \le b_i -\epsilon + M_i y_i \quad \forall i$$and $$\sum_i y_i \ge 1.$$ $M_i$ is a "large enough" positive constant for each $i$. The objective function can be pretty much anything.

$\endgroup$
1
  • $\begingroup$ Thanks a lot. $P_{A}$ and $P_{B}$ are always bounded. $\endgroup$
    – Duh Huh
    Nov 24 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.