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

learn more… | top users | synonyms

1
vote
1answer
371 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
1answer
267 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq ...
0
votes
1answer
36 views

Travelling salesman problem as an integer linear program

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear ...
0
votes
0answers
114 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
0
votes
2answers
789 views

GameTheory, Solve for optimal strategies by solving a system of linear equations

In a book on game theory I saw the following example of a game, a modified version of Roshambo (or Rock-paper-scissors), which is described by the following payoff-matrix: $$ \begin{array}{c|c|c} ...
0
votes
0answers
678 views

non-degeneracy in linear programming

How to do the sum? Consider the standard form polyhedron $P = \{\mathbf{x} | A\mathbf{x}=\mathbf{b}, \mathbf{x} \geq 0\}$. Suppose the matrix $A$, of dimensions $m \times n$,(m<=n) has linearly ...
3
votes
1answer
292 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
2
votes
1answer
61 views

How can I determine B-inverse from an optimal tableau of a LP?

(This is NOT a homework question, I am reviewing for my upcoming exam) Given this linear program: and this optimal tableau: I am attempting to determine $B$ inverse using the table above. From ...
2
votes
1answer
129 views

Formulating an LP problem with vectors

We have $m$ vectors $v_1,v_2,\dots,v_m\in\mathbb{R}^n$ and $m$ numbers $t_1,t_2,\dots,t_m\in\mathbb{R}$ and we want to find a vector $y\in\mathbb{R}^n$ such that $$|v_i^Ty-t_i|\leq D$$ for ...
2
votes
2answers
572 views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
2
votes
1answer
77 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at ...
2
votes
1answer
163 views

Previous table of simplex algorithm

I have this problem of simplex method which shows cycle . Problem : Maximize $Z=10x_1-57x_2-9x_3-24x_4$ Constraint to : $ 0.5x_1-5.5x_2-2.5x_3+9x_4<=0 $, $ ...
2
votes
1answer
525 views

Reconstructing an optimal Simplex tableau from an optimal solution

I have here a bounded LP with infinite optimal solutions: ...
1
vote
1answer
123 views

Tutorial for Simplex Method with No Slack Variables

I found a nice tutorial here http://www.math.ucla.edu/~tom/LP.pdf for applying the Simplex Method to problems of the form: maximize $c^T x$ with the constraints $Ax\leq b$, $x_i \geq 0$. It suggests ...
1
vote
1answer
42 views

Real linear combinations of intervals

Given intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1<1$ and a third interval $I=[-a,a]$ where $0<a<{1}$, when is there an $\alpha,\beta\in\Bbb R$ such that $\alpha I_0 ...
1
vote
1answer
120 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
1
vote
1answer
71 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
1
vote
1answer
216 views

Computationally proving a linear programming solution is unique?

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, ...
1
vote
0answers
66 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
215 views

simplified Linear programming model with time constraints

Based on my other question, here is a simpler hypothetical exercise that isolates that time constraint issue all together: A farmer has 1000 ha forest that is already at a mature age assumed to be ...
1
vote
0answers
412 views

Showing a dual LP solves a primal LP

I originally asked this question: Does solving the LP dual SOLVE the primal LP? It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
1answer
120 views

Linear programming duality theorem

As far as I know, there are 2 versions of this theorem: 1) $\max \{xc^T: xA \le b, x \ge 0, x \in R^n\} = \min \{by^T: Ay^T \ge c^T, y \ge 0, y \in R^m\}$ 2) $\max \{xc^T: xA \ge b, x \in R^n\} = ...
1
vote
2answers
718 views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
1
vote
0answers
167 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
1
vote
1answer
357 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
1
vote
0answers
54 views

A question about $n\times n$ matrix [duplicate]

Possible Duplicate: For every matrix $A\in M_{2}( \mathbb{C}) $ there's $X\in M_{2}( \mathbb{C})$ such that $X^2=A$? Square root of a matrix Let $A$ be $n\times n$ matrix on $\mathbb ...
1
vote
2answers
928 views

Optimizing with Absolute Value Objective Function

max : $w = |q^T y|$ subject to $A y \leq b$ $y \geq 0$ Please describe how one could solve the non-linear programming prob. above by using linear programming methods. I tried changing $y$ to $y' ...
0
votes
1answer
56 views

Derive this variant of Farkas' lemma, through another variant of Farkas' lemma.

Derive the following variant of Farkas' lemma: For each $mxn$ matrix A and vector $b\in\mathbb{R^m}$ one of the following statements is true: $\exists x\in\mathbb{R^n}$ such that $Ax=b$ $\exists ...
0
votes
0answers
22 views

Find if an integer can be written as a sum of n positive integers with only k unique integers k<=10

Given a set of $n$ positive integers $A$ ($n \leq 10^4$), where the number of unique integers is $k$ ($k \leq 10$), I need to find if a positive integer $W$ can be written as a sum of a subset of the ...
0
votes
1answer
30 views

Integer Points in Simplex

Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the $\ell_1$-ellipse with semi-axes of length ...
0
votes
1answer
65 views

How do I convert this into a linear programming problem?

A farmer is planning to raise wheat and barley. Each acre of wheat yields a profit of \$50 and each acre of barley yields a profit of \$70. To sow the crop, two machines, a tractor and tiller, are ...
0
votes
2answers
43 views

LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron

I've encountered the following question which I am unable to solve: $$ P = \{\vec x | A\vec x \geq \vec a\} \\ Q = \{\vec x | B\vec x \geq \vec b\}\\ P, Q \subseteq R^n $$ Find an algorithm to ...
0
votes
1answer
3k views

Finding the number of basic/zero variables at an optimal corner point in linear programming

Draw a graph of the following problem $$\begin{align}4x+3y &\leq 180 \\ 7x+4y &\leq 280 \\ y &\leq 40 \\ x &\geq 0 \\ y &\geq 0\end{align}$$ a) If the problem is to ...