The tag has no wiki summary.

learn more… | top users | synonyms (1)

4
votes
1answer
3k views

Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
7
votes
3answers
3k views

Solving a system of linear inequalities — what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$? For the applications I have in mind the ...
4
votes
2answers
3k views

Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations

Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations ...
1
vote
1answer
461 views

When is a triangular matrix totally unimodular?

I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
5
votes
1answer
247 views

Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
1
vote
0answers
3k views

A system of linear equations with linear constraints

Mathematical problem. Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of ...
2
votes
0answers
534 views

Is it possible to use linear programming to solve this problem?

I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group. Could someone comment on whether this is ...
2
votes
3answers
491 views

A simple infinite dimensional optimization problem

I'd be grateful for a reference for the following result, which I believe to be true, and should be well-known. Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
23
votes
5answers
4k views

How to find a closest integer point to intersection of two lines?

Hello. Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it). We're given two lines on the plane, each of them has at least two integer points ...
1
vote
0answers
1k views

Covariance matrix formula interpretation - what am I missing?

I'm reading a paper that outlines the calculation of a covariance matrix like the following: $C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$ What is the order of this matrix? My interpretation ...
1
vote
4answers
2k views

Linear programming piecewise linear objective

I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this: max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$ $s.t. $ ...
10
votes
1answer
1k views

Sum of difference moduli vs. sum of modulus differences

This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself. Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
11
votes
3answers
683 views

Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$ This can be done efficiently by linear programming (time polynomial in ...