Questions on linear programming, the optimization of a linear function subject to linear constraints.
1
vote
1answer
49 views
Wealth indicator function for bidder agent logic
I want to create a wealth indicator function used by the logic of a bidder agent, that tells the agent if he's rich (in comparison to others).
Given:
Total number of competitors $n$
Amount of all ...
1
vote
1answer
30 views
Compute $v,W,k$ such that the following is true
$$
\left\{ x \in \mathbb{Z}^4 |
\begin{pmatrix}
5 & 3 & 7 & 0 \\
2 & -4 & 6 & 5
\end{pmatrix}
x =
\begin{pmatrix}
5 \\0
\end{pmatrix}
\right\} = \left\{ v + Wy \ | \ y \in ...
1
vote
1answer
34 views
How to construct an LP problem that makes a (partial) theorem fail?
I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem.
The theorem is Theorem ...
1
vote
0answers
33 views
Model Linear-Programming Problem
A factory needs to complete $n$ jobs by using $m$ machines. To complete each job $j, j=1,\dots,n$, an amount of $r_j\geq 0$ processing units is required. Each machine $i$ has a processing speed ...
0
votes
0answers
18 views
finding the optimal solution of the dual problem
This is homework.
I have the following dual problem, formed by using lagrangian relaxation.
$$
\begin{align}
min & \{&89y_1 +&3y_2 +&10y_3\}\\
s.t.& &3y_1+& &y_3 ...
0
votes
0answers
18 views
Prove that this linear programming problem has the following dual problem
Consider the following Linear Programming problem:
$$max \sum_{j=1}^nc_jx_j$$
\begin{align} s.t. \quad
\sum_{j=1}^na_{ij}x_j=b_i \quad 1\leq i\leq m\\
x_j\geq 0 \quad 1\leq j \leq n.\\
...
1
vote
2answers
36 views
Linear programming problem neither max nor min
Heres the actual question:
television provider broadcasts two movie channels, A and B. Channel A broadcasts 1 romantic
movie, 3 action movies and 3 comedies per month at a cost of 50 Euro. ...
1
vote
1answer
206 views
Convex hull of sets defined by (in)equalities
If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to ...
0
votes
1answer
40 views
Construct a linear programming problem for which both the primal and the dual problem has no feasible solution
Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution.
For ...
0
votes
0answers
32 views
Basic Solutions in Linear System
I am studying Linear programming and we have just learnt about Basic solutions. I know that a basic solution (x) should have 2 properties:
should indeed be a solution. $Ax = b$ should hold.
for some ...
0
votes
1answer
200 views
Linear Programming question
I am kind of lost on this problem and would like it if I can get help on this.
Matching Pennies. In this simple two player game, the players (call them R and C) each choose an outcome, heads or ...
0
votes
1answer
38 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 ...
1
vote
1answer
16 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 ...
1
vote
1answer
152 views
MATLAB LP formulation of investment problem (in Bertsimas' lecture notes)
I wish to write MATLAB codes to solve the following linear programming problem found in Bertsimas' lecture notes:
My attempt was as follows (sequence of variables for f' is A, B, C, D, E, Cash1, ...
4
votes
0answers
106 views
Can you verify a Wikipedia article I wrote? [closed]
I'm a college student in a country of Serbia (South East Europe) studying IT and CS, and for one of the courses I have an asignment to do. The assignment is to make a good, standards following, ...
0
votes
1answer
21 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?
3
votes
1answer
120 views
Dimension of solution space for system of linear inequalities
Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise ...
0
votes
0answers
12 views
Whats the deal with phase 1 of 2 phase simplex?
I have been reading online to brush up on my linear programming and I tend to find that people have so many different versions of going about the same thing, its frustrating partly because I don't see ...
0
votes
0answers
13 views
How to add artificial variables to a linear programming matrix
I was working on a linear programming assignment where we are given (via textfile) A, b, c and need to solve the problem:
Max c^t * x (c-transpose x)
such that Ax = b
Now if I recall correctly: ...
2
votes
2answers
35 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
0answers
27 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
23 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?
0
votes
1answer
25 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 ...
1
vote
2answers
126 views
Removing linear redundant constraints using Gauss Elimination
I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar ...
2
votes
1answer
42 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 ...
2
votes
1answer
127 views
Simplified nurse scheduling problem
I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which ...
0
votes
0answers
16 views
linear programing vs. dynamic programing
Is there any similarity or dual principle between both linear programing and dynamic programing ? Any prove or an example would be wonderful.
e.g. can I present this problem as dynamic programing:
...
1
vote
1answer
47 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 < ...
1
vote
1answer
69 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 ...
0
votes
1answer
22 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
0answers
20 views
Job assignment problem
I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
0
votes
1answer
28 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
33 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 ...
0
votes
0answers
20 views
Proof by Farkas theorem
2) Show using duality that exactly one of the following systems has a solution:
I) Ax=b, 0 ≤ x ≥ e
II) A^T u + v ≥ 0, b^T u + e^T v=-1,v ≥ 0
Solution:
(P) ...
0
votes
1answer
174 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.
...
0
votes
1answer
49 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 ...
0
votes
0answers
29 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 ...
-1
votes
0answers
61 views
Proof mathematically [closed]
Can anyone prove it mathematically, please help?
Consider the following linear programming problem:
Min $z=c^Tx$ such that $Ax=b, x\ge 0$. Here $c,x$ are $n\times 1$ matrices, $b$ is a $m\times 1$ ...
1
vote
3answers
2k views
Primal- degenerate optimal, Dual - unique optimal
Simple question-
Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
0
votes
1answer
41 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
42 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 ...
1
vote
0answers
33 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
1answer
44 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 ...
0
votes
0answers
30 views
Fourier Motzkin Elimination for Linear Program
I am trying to solve an LP using Fourier Motzkin elimination. I know that it is not very efficient for LPs but I want to understand how it works in cases where I do not face the worst case(Every ...
1
vote
1answer
256 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
0answers
13 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
161 views
A variation of the Assignment Problem
In the following Wikipedia article about the Assignment Problem in the Example section, it says:
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
0answers
21 views
Linear Programming problem with n variables
Consider a linear programming problem with n variables in standard form. Explain why a non-negative solution to $m$ $\le$ $n$ equality constraints in which at least $n - m$ variables are zero ...
3
votes
1answer
93 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 ...
6
votes
1answer
391 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 ...
