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

learn more… | top users | synonyms

0
votes
1answer
70 views

Finding a dual Linear-Program

We are trying to prove Von-Neumann's MINIMAX Theorem namely $$\max_{x\in\Delta_{n}}\min_{y\in\Delta_{m}}y^{T}Ax=\max_{x\in\Delta_{n}}\min_{1\leqslant i\leqslant n}(Ax)_{i}$$ (Here $\Delta_k$ is the ...
1
vote
1answer
184 views

Farkas lemma variations

Suppose the system: $Ax=0,x \geq 0, $ and $c \cdot x > 0$ does not have a solution. How can I apply Farkas' lemma to create a system that must have a solution? I'm not so sure how to proceed, ...
3
votes
1answer
37 views

Is it necessary to state that $y_i \leq 1$

In a class test for Linear Programming, my professor deducted some marks because I missed the condition $y_i \leq 1$ in the mixed strategy games solution. $ y_i $ stands for the probability of any ...
1
vote
0answers
215 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
0answers
89 views

Linear Programming: Modifying Coefficients of the Objective Function

Consider a final tableau with entries: Row 1: 0,(-1/2),1,1,2,0,-1 Row 2: 1,(1/2),0,2,-1,0,-2 Row 3: 0,2,0,-1,(-1/2),1,3 Basic variable values (4,2,1) and objective function coefficients ...
1
vote
1answer
178 views

Linear Programming for Integer Solutions

Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer. How would one manipulate the resources so that the ...
7
votes
2answers
319 views

Finding the payoff matrix of a game

A two player zero-sum game can be represented by a $m\times n$ payoff matrix $M$ having $m$ rows and $n$ columns with values in $[0,1]$. The value $M(x,y)$ represent the payoff given to player $1$ ...
1
vote
1answer
211 views

How to prove this? The existence of solutions to linear inequalities

A system of real homogeneous linear inequalities $\lambda_i>0$, $i=1,2,\ldots,m$, has a solution if and only if there is no nontrivial linear dependence with nonnegative coefficients among the ...
0
votes
2answers
34 views

What are the constraints on this system

A company produces 2 types of frames, an ATB frame and a race frame For the ATB frama you need 4kg of aluminum and 6kg of steel, for the race from you need 5kg of aluminum and 2kg of steel. They ...
1
vote
1answer
211 views

Drawing in 3 dimensions: Feasible region

We have the following constraints: $$ 0 \leq x \leq 10$$ $$ 0 \leq y \leq 20$$ $$ 0 \leq z \leq 25$$ $$ 0 \leq x + y + z \leq 15$$ We have to draw this in an 0xyz - coordinate system, I did the ...
3
votes
1answer
203 views

Linear Programming question - Optimal solution

In Linear programming, you want to optimize stuff. For example; minimize the costs and maximize the profit. We have a series of constraints, in my case on either 2 or 3 variables. You can draw them in ...
4
votes
2answers
212 views

Wolves and chicks puzzle

This problem is from the handheld video game, Professor Layton and the Curious Village. I think the solution is very cool, but more than that, I want to know how to show that the minimum number of ...
0
votes
2answers
73 views

Checking the existence of a solution for a set of linear equality and ineaulity equations

I would like to know if there is a method to check the existence of the solution for a given set of linear equations composed with both equalities and inequalities? I'm not interested in the solution, ...
2
votes
1answer
179 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
1
vote
2answers
292 views

Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

So, there are four inequalities: $$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$ If we draw all those ...
0
votes
1answer
107 views

Bounded and Feasible of Linear Program?

I have a question on usage of terminology in Linear programming. Why do we have terms like "If an LP is bounded and feasible, then..." My confusion is, if a Linear program is bounded then it has to ...
0
votes
0answers
34 views

Please help with the LP formulation

I would like to formulate the following constraints as a Linear constraint $|x_1-y_1| + |x_2-y_2| + |x_3-y_3| > |\sum_{i=1}^nx_i- \sum_{i=1}^ny_i|$ $ \bf{x,y} \in \bf{R}^n $ Basically I am ...
0
votes
1answer
662 views

How to a plot a line for ax+by-c in MATLAB?

The title basically says it all. I'm doing an assignment and need to include a plot of my scatter and the line generated by linprog(). I ran ...
2
votes
0answers
48 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
87 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 ...
1
vote
2answers
184 views

Alternative function notation?

I have a professor that uses the notation $$ \lambda (x_1,x_2,\dots ,x_n)\ . \ c_1x_1 +c_2x_n + \dots +c_nx_n \colon \ \mathbb{R}^n \longrightarrow \mathbb{R}$$ for a function $$ f \colon \ ...
1
vote
1answer
71 views

What does multilinear function mean?

A draft research paper claims that $Q(p)=1-p_1 p_2 p_3 p_4 - p_2 p_3 p_6 p_7-p_1p_2$ is multilinear where $p_i = \mathbb P(e_i)$ and $e_i$ is a basic event of a component to fail. I have learnt in LP ...
1
vote
1answer
52 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
2
votes
2answers
59 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
1
vote
1answer
73 views

Criterium for Nash-Equilibrium from Nash's Paper

I am reading Nash's original paper "Non-cooperative games" from 1951, which could be found here: Non-Cooperative Games, Nash (1951) Now I have a question to criterion (2) on the second page. There ...
0
votes
1answer
102 views

Duality in linear programming

I saw the some theorem. If primal problem is unbounded then no feasible solutions for dual. If dual problem is unbounded then no feasible solutions for primal. Please help me to understand above ...
0
votes
1answer
197 views

Different formulation of a Traveling Salesman Problem

Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions: for ...
2
votes
2answers
2k views

Nash Equilibrium for the prisoners dilemma when using mixed strategies

Consider the following game matrix $$ \begin{array}{l|c|c} & \textbf{S} & \textbf{G} \\ \hline \textbf{S} & (-2,-2) & (-6, -1) \\ \hline \textbf{G} & (-1,-6) ...
1
vote
1answer
124 views

Linear programming problem

Some additional information: In the next season the harvesting amount is estimated at 900 for farm A, 1200, 1500, 1800 for farm B,C and D respectively. In this scenario I'm asked to minimize the ...
0
votes
2answers
107 views

Find $n$ in $8n^2 \le 64n\lg n$

Given the solution. Can someone help me why $n \le 43$. What is the step by step of the solution for this?
4
votes
0answers
54 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?
0
votes
1answer
115 views

Is the product of two totally unimodular matrices again totally unimodular?

For unimodular matrices this is the case. It seems reasonable that this is also the case for totally unimodular matrices, but I couldn't find a reference for this. Does someone know why it is true ...
1
vote
1answer
166 views

Are there 0-1-matrices that are not unimodular?

I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...
1
vote
1answer
59 views

linear equivalent min{} constraint

Activities are assigned to venues. Each activity $a_i$ has maximum size $b_i$ and demand $c_i$. Each venue $v_j$ has maximum size $d_j$. An activity can be assigned to multiple venues, and we need to ...
0
votes
2answers
581 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} ...
2
votes
1answer
433 views

How to solve this LP problem as a Dynamic Programming problem?

The standard form LP problem is $$\min -3x_1-7x_2-10x_3 \text{ s.t. }$$ $$x_3\leq 2$$ $$40x_3+40x_2+20x_1\leq 180$$ $$x_1,x_2,x_3\geq 0$$ My last lecture covered the Bellman equation ...
1
vote
1answer
113 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\} = ...
0
votes
1answer
1k views

Example about the Reduced cost in the Big-M method?

I want to gather examples about the reduced cost in different cases, now for the Big-M method. I hope this makes the methods more accesible. So How does the Big-M method work with the below? ...
1
vote
1answer
310 views

Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...
1
vote
1answer
495 views

Reduced cost in the Phase II of the two-phase Simplex?

My lecture slides outline how the two-phase simplex works: this table shows the end result of the phase I for the standard-form problem and the auxliary table of the phase I here. I understood until ...
0
votes
1answer
356 views

Reduced cost vector in the phase I of the Two-phase simplex?

I am trying to understand the part in red. The left is the standard form problem and the right is the auxiliary problem. Now I can understand until the red i.e. $\bar c =(-1,-1,-3,-1,-2,0,0,0)$. The ...
6
votes
1answer
79 views

Bounding the number of nonzero coefficients in a conic combination

I'm looking for a proof for the following statement in order to understand a proof about integer programming I'm reading. Given vectors $x_1, \ldots, x_s \in \mathbb R^n$, nonnegative coefficients ...
0
votes
1answer
26 views

Is it possible to slove problem with norm constraints using only linear programming?

The problem is $\min_x w^Tx$ s.t. $Ax=b$ $||x||_2=1$ Is there any tricks to handle the norm constraints such that the problem can be solved by only using linear programming tools?
0
votes
1answer
64 views

Optimum exists but not extreme point in Standard Form LP problem?

Standard form problem $$\min \bar c^T \bar x \text{ so that } A \bar x=\bar b, \bar x\geq \bar 0$$ I am thinking the point II (Finnish) i.e. optimum exists but it is not extreme point, why it ...
3
votes
1answer
472 views

Linear programming problem with no objective function

I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize. I've been ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
1
vote
1answer
31 views

-$\infty$ cost in unconstrained LP problem?

I am trying to understand this lecture slide (Finnish) and the point in bold. It is a part of an OR condition, this is how I understand it. I cannot understand the optimal cost statement. Example ...
0
votes
0answers
81 views

linear equations with inequality constraints

The problem is, given a set of linear equations $Ax=b$ such that the system is under-determined, and a set of linear inequalities $Cx\geq 0$, find a solution for the system. Does anyone know a general ...
0
votes
2answers
162 views

Is an unit-cube polyhedron? What about other platonic solids?

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in ...
2
votes
1answer
50 views

What is the solution according to the following parameters? (equation)

The equation would accept x,y and output z where As X approaches infinity and Y approaches infinity, Z approaches 0 As X approaches infinity and Y approaches 0, Z approaches 0 As X approaches 0 and ...