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

learn more… | top users | synonyms

1
vote
1answer
106 views

Minimizing deviations from threshold value from a given group of numbers

Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
0
votes
1answer
118 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
0
votes
1answer
190 views

How to linearize the following LP

I want to minimize $|d_1-d_2|+e1+e2+e3$ where $d_1,d_2,e_1,e_2,e_3>=0$ and $|.|$ denotes the absolute value, for some linear constraints. Is there any way I can linearize the objective function?
1
vote
0answers
40 views

What are the available libraries or programs for finding extremes of a function with no symbolic definition?

In my current mathematical inquiry, I would like to gain insight on behaviour of a $d$-dimensional continuous function by locating its maximum over the hyperplane $\sum_{i=1}^d x_i = 1$ for $x_i$ ...
0
votes
2answers
584 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
2
votes
1answer
174 views

Show that two Linear Programming problems are equal

Consider the general linear programming problem $min \sum_{j=1}^n c_jx_j$ s.t. $\sum_{j=1}^n a_{ij}x_j \leq b_i$, for $i=1,\dots , m$ $x_j \geq 0$ for $j=1,\dots , n$ And the ...
0
votes
1answer
158 views

How to solve an underdetermined linear system with variables limited to an interval

If I have an underdetermined linear system of equations, with the additional constraint that all of the variables are limited to the interval $[0, 1]$, what techniques are there to solve this in the ...
2
votes
2answers
397 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
1
vote
1answer
292 views

Strict inequality in MILP

I have a problem with the following constraint. There are 2 variables $p \in [0,1] \subseteq \mathcal{R}$ $\sigma \in [0,1] \subseteq \mathcal{Z}$ The constraint over the variables is $c - p < ...
0
votes
1answer
38 views

How to solve Linear programs of the form Maximize v

I face difficulties in solving LPs in the form Maximize v subject to: a11x1+a12x2<=v ...........<=v The v is the variable I want to maximize. Should I ...
0
votes
1answer
89 views

Show using duality that exactly one of the following systems has a solution

(I) $Ax=b$ ; $0≤ x ≤e$ (II) $uA +v ≥0 ; ub + ve = -1 ; v ≥ 0$
1
vote
0answers
77 views

Prove mathematically

Q.1 Consider the dual simplex method applied to a standard form problem with linearly independent rows. Suppose we have a basis which is primal infeasible, but dual feasible, and let i be such that ...
1
vote
0answers
185 views

Strictly Dominated and Never Best Response in LP

There is a well known notion of Strategic Dominance in Game Theory. I am interested in elimination of strictly dominated strategies by Linear Programming and in LP for definition of never best ...
0
votes
1answer
846 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 ...
1
vote
1answer
193 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
2
votes
0answers
51 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 ...
0
votes
1answer
250 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
1
vote
1answer
1k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
1
vote
0answers
20 views

Issues with solving large sparse linear equations

I have some issues solving sparse linear equations Ax = b My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
2
votes
1answer
271 views

Simplex on Linear Program with equations

My linear program instead of inequations also contains one equation. I do not understand how to handle this in every tutorial I searched the procedure is to add slack variables to convert the ...
1
vote
1answer
35 views

How to calculate the variance of linear prediction parameters?

I'm using linear prediction with singular value decomposition (LPSVD) to analyze signals that are damped sinusoids. If my understanding of the theory of linear prediction is correct (and it may not ...
3
votes
1answer
140 views

Correctness of these linear programming formulations

Problem: A Company can use 3 different procedures to produce a product, for the production of every product are necessary 3 machines as below: The numbers relate the hours necessary. every ...
4
votes
1answer
332 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
2
votes
1answer
127 views

Is this linear programming?

I have the following problem and I'd like to know if it is formalizable as a LP program. (or, more generally, if it is solvable in polynomial time). Let us fix some terminology first which will ...
0
votes
1answer
32 views

Find a point in a polytope that always cuts off a constant fraction of the polytope.

I have $k$ linear inequalities in $\mathbb{R}^n$, which we can express as $Ax \ge c$ (where $A \in \mathbb{R}^{k \times n}$ and $c \in \mathbb{R}^k$). Assume that the set of $x \in \mathbb{R}^n$ that ...
0
votes
1answer
27 views

Compute the point of contraction of a bounded region in $\mathbb{R}^n$

Say we have a list of linear inequalities that define a bounded region in $\mathbb{R}^n$. These inequalities are: $a_1 \cdot x \ge c_1, \dots, a_k \cdot x \ge c_k$. Assume general position (i.e. it ...
0
votes
1answer
64 views

Graphical solution of LOP with three variables and a parameter

For what values of $\lambda$ does the following linear optimization problem has no solution? $$ x_2 - \lambda x_3 \to \operatorname{min} $$ subject to \begin{align*} -x_1 + 3x_2 + x_3 & ~=~ 3 \\ ...
0
votes
1answer
71 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
194 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
225 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
91 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
185 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
326 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
217 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
35 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
221 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
214 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
221 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
74 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
184 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
320 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
110 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
35 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
726 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
49 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
93 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
194 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
73 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
53 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 ...