Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

6
votes
0answers
735 views

Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
6
votes
0answers
87 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
4
votes
0answers
62 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
4
votes
0answers
491 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} ...
4
votes
0answers
50 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
3
votes
0answers
168 views

The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that: For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex ...
3
votes
0answers
57 views

On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align} \begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; ...
3
votes
0answers
109 views

weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if x and p are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
3
votes
0answers
49 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: ...
3
votes
0answers
61 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
3
votes
0answers
228 views

Bender's Decomposition for Mixed Integer Programs

Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1). $LP_1$ has the form ...
3
votes
0answers
456 views

How to Minimize A Function Where The Number of Variables is Unknown

I have a standard linear programming problems I want to solve: $$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
2
votes
0answers
25 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
2
votes
0answers
29 views

Rayleigh Quotient variant?

If $A$ is a covariance matrix and I want to get $\max X^TAX$ where each value of $x$ is between -1 and 1. Is there a closed-form solution for this? I understand when $X^TX = 1$ this becomes the ...
2
votes
0answers
23 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
2
votes
0answers
65 views

Post-optimality analysis: Change in one of the constraints

Consider the LP: max $\, -3x_1-x_2$ $\,\,$s.t. $\,\,\,\,$ $2x_1+x_2 \leq 3$ $\quad \quad \ -x_1+x_2 \geq 1$ $\quad \quad \quad \quad \ > x_1,x_2 \geq 0$ Suppose I have solved the above ...
2
votes
0answers
21 views

Determining maximum number of groups - maybe Linear Programming

Given a set D dogs, C cats, and B birds, for each dog d in D, there is a set c(d) which indicates the set of cats that dog d likes and a set b(d) birds that dog d likes. How do I find the maximum ...
2
votes
0answers
47 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
2
votes
0answers
49 views

Assigning jobs to minimize cost - Linear programming

I'm stuck trying to solve this linear programming question. You want to make a website with a list of features F, which are n elements long. Each feature has a corresponding value for how long it'll ...
2
votes
0answers
62 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
2
votes
0answers
129 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...
2
votes
0answers
78 views

Higher dimensional Euclidean geometry problem

In my engineering/physics research, I am facing one math problem which I believe should be well established in mathematics... I have a linearly spanned space given by the column vectors of the ...
2
votes
0answers
33 views

Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
2
votes
0answers
50 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
2
votes
0answers
35 views

Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
2
votes
0answers
240 views

Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
2
votes
0answers
168 views

solving linear programming with time constraints

NOTE: I added the following new question that simplifies the problem and attempts to isolate my issues with the time variable I have a linear problem that I'd like to solve with the following ...
2
votes
0answers
75 views

Existence of a Linear Optimization Problem

I am working on a linear static optimization problem. I found a solution to the problem. However, I want to formally check the solution existence. I tried some methods but I don't know if it is enough ...
2
votes
0answers
50 views

Explicitly solving linear programming problems

Linear programming problems generically involve the use of a repeated algorithm to solve. Is there a reason they can't be solved algebraically/formulaically? Ex: Minimize x1 + x2 + x3.... x1, x2, ...
2
votes
0answers
37 views

How to visualize duality

In My course of linear programming we are given the definition of a primal/dual problem. However I cannot really get my heard around what it actually is? It helps us in later exercises. Are we ...
2
votes
0answers
47 views

Linear Program Transformations

I have a Linear Program with constrains of the form: $$a_{11}x_1+a_{12}x_2+\ldots\le 0$$ $$a_{21}x_1+a_{22}x_2+\ldots\le 0$$ $$a_{31}x_1+a_{32}x_2+\ldots\le 0$$ My problem is that if I try to ...
2
votes
0answers
46 views

Put positive polynomial in finite intersection of half-spaces

Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, with rational coefficients. Thus ${\mathcal P}_{n,d}$ had dimension $\binom{n+d}{n}$ over $\mathbb ...
2
votes
0answers
68 views

Need help finding unknowns in simplex tableau.

I need help with this homework problem. The objective is to maximize $2x_1 - 4x_2$, and the slack variables are $x_3 and x_4$. The constraints are $=<$ type. Tableau $\begin{matrix}z & x_1 ...
2
votes
0answers
146 views

fundamental theorem of linear inequalities

Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...
2
votes
0answers
140 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
2
votes
0answers
330 views

Reconstructing an optimal Simplex tableau from an optimal solution

I have here a bounded LP with infinite optimal solutions: ...
2
votes
0answers
153 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
2
votes
0answers
86 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
2
votes
0answers
110 views

Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
2
votes
0answers
78 views

Feasibility checking

I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution. 1- What is the best worst case running time for this decision ...
2
votes
0answers
105 views

Linear optimization, homework problem.

Please help with the following problem: Given a $m$ x $n$ matrix $A$, $m$-vectors $b$ and $y$, and $n$-vectors $c$ and $x$. Write the dual $LP$ problems $P$ and $P^d$ in the standard form. Whether ...
2
votes
0answers
152 views

Linear optimization problem.

I have copied the entire problem from the book. It has 7 parts. Please show me how to do any 1-2 of the parts. I mostly understand the problem, but need to see a fully woked out problem. Given a $m$ ...
2
votes
0answers
279 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
2
votes
0answers
130 views

Mathematical Programming Community

Is there a good online community for discussing optimization models? The ones I have found don't seem to have a critical mass for active discussions.
1
vote
0answers
55 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
0answers
29 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
1
vote
0answers
11 views

How to import matrix from sif document

I want to make some computation (with scilab, scipy or other) over the matrix A of linear problems (in inequational form). Those problems are in .sif format (from the netlib library in fact) and I ...
1
vote
0answers
19 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
1
vote
0answers
9 views

Symbol or name for Basismatrix of Linear Programming

This question is about the Basismatrix in the context of Linear Programming. Basically (haha!) we have the Matrix of the standard (or normal) form, which consists of (A|E) with the coefficient matrix ...
1
vote
0answers
27 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...