Tagged Questions
1
vote
2answers
33 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
15 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
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 ...
0
votes
2answers
22 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
24 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 ...
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
1answer
27 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 ...
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 ...
1
vote
1answer
68 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
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 ...
1
vote
0answers
35 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
44 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 ...
0
votes
0answers
27 views
Example of delayed column generation
Can someone point me to a small example of how delayed column generation works for the cutting stock problem. I have found several sources that describe it abstractly but I still don't understand ...
4
votes
2answers
122 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 ...
1
vote
2answers
80 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
0answers
27 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 ...
1
vote
1answer
39 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
54 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}$
?
0
votes
1answer
40 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
79 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 ...
1
vote
1answer
236 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$ ...
3
votes
2answers
106 views
Find the point in a sub-space defined by linear constraints closer to an external point
I have the following
$P \in \mathbb R^d$
A set of $k$ linear constraints $c_i \in \mathbb R^d,d_i \in \mathbb R$
I need to find the point $P_0$ that satisfies all the $k$ constraints (i.e. ...
2
votes
1answer
29 views
Smooth Reformulation of NonSmooth Constraints
If I have something like :
\begin{align}
\min_x \max_i f_i(x)
\end{align}
I can reformulate this nonsmooth formulation as:
$$\min_x z$$
$$z\geq f_i(x)$$
and I have a smooth formulation of the problem.
...
2
votes
0answers
55 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
1answer
76 views
Optimality Criterion and the Simplex Method
The optimality criterion states:
If the objective row of a tableau has zero
entries in the columns labeled by basic variables and no
negative entries in the columns labeled by nonbasic variables,
...
0
votes
0answers
23 views
Constraint needs to be written as a semidefinite matrix
Is it possible to transform the inequality $v^2-cd\geq 0$ , $c\geq 0, d\geq 0$ to a semidefinite constraint needed for a Semidefinite programming problem?
Thanks!
0
votes
0answers
36 views
Uncertaint linear program
I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It ...
1
vote
1answer
60 views
Warehouse Location Problem as an integer progam instead of a mixed-integer program
Given a set of costumers $M = \{1, \dots , m \}$ and a set of of factories $N = \{1, \dots , n\}$ we have
$c_{ij} \geq 0$ costs to deliver to costumer $i \in M$ from factory $j \in N$
$F_j \geq 0$ ...
1
vote
0answers
134 views
Defining Dual problems in Linear programming optimization
I have this Primal problem:
$
Max \sum\limits_{i=1}^{50} X_iC_i \\
S.T.\\
\sum\limits_{i=1}^{50} X_iw_i\le W \\
\sum\limits_{i=1}^{50} X_iV_i\le V \\
X_i \le 1 \\
X_i \ge 0 \\
$
Now according the ...
1
vote
0answers
38 views
optimization of number of cylinders in a cube
I must admit that mathematics is not quit my strongest skill, so I want to ask you from where should I start with a kind of simple problem. Please keep in mind that I'm just a newbie asking things ...
1
vote
0answers
33 views
LP to test if two Line Segments intersect
I would like to use a linear program to test if two given linesegments $\overline{ab}$ and $\overline{cd}$ do not intersect.
In a high level description I would have an LP of the form
$$min ...
2
votes
1answer
79 views
Minimim steps required based on game logic
I have the following simple game logic.
You start with G gold and 0 experience at Time = 0 minutes.
There are different types of houses what you can build, each with his own properties.
House A ...
1
vote
0answers
123 views
Linear programming: writing a problem with artificial variables?
Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
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
1answer
53 views
Is this use of the simplex method correct?
I am trying to implement a simplex algorithm for solving LP task. I will post the question and my solution as well - what I need to know is whether my solution is correct, thanks in advance!
...
0
votes
0answers
55 views
closed form of a linear program
I have a linear program:
$\min. L(b_{ij})=\sum_i\sum_j w_{ij} b_{ij}$
subject to
$\ 2 \leq \sum_j b_{ij} \leq 3 \ \ \ \forall i$
$ \sum_i b_{ij} = 1 \ \ \ \forall j$
$0\leq b_{ij}\leq1$
...
2
votes
3answers
79 views
Dual of a Linear Program
\begin{align}
\min_{x} c^Tx \\
s.t.~Ax=b
\end{align}
Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by
\begin{align}
\max_{\lambda} \lambda^Tb \\
...
1
vote
1answer
88 views
Linear programming - task formulation
I have a question concerning the formulation of a linear programmign task. I am trying fo find $x^* \in argmax_{x \in R^n}\{ a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5 \}$, subject to ...
2
votes
2answers
183 views
What are the advantages of dual of a problem
I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
3
votes
4answers
235 views
Finding minimal cost edge cover for a bipartie graph
I have got two sets of elements and a pruned graph of bipartie edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
2
votes
0answers
53 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 ...
0
votes
2answers
165 views
Convex function from Hessian
Am I correct to say that the following function is convex?
$$\begin{align}
& f(x,y)=-\sqrt{xy} \\
& x>0,y>0 \\
\end{align}$$
After computing the Hessian:
$$ Hf =\left[ \begin ...
3
votes
1answer
197 views
Duality. Is this the correct Dual to this Primal L.P.?
Given a problem:
Find the dual:
$$
Primal =\begin{Bmatrix}
max \ \ \ \ 5x_1 - 6x_2 \\
s.t. \ \ \ \ 2x_1 -x_2 = 1\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\
...
2
votes
1answer
86 views
Critical Points. Find and classify.
Given $g(x,y)=y^2 - x^3$
find the critical points and classify them
$$\nabla g(x,y) = \begin{pmatrix}
-3x^2 \\
2y \\
\end{pmatrix}$$
So,
$\implies -3x^2=0,2y=0$
...
1
vote
2answers
133 views
How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?
I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that
$$\bar g=\begin{pmatrix}
(x_1+2)^2+(x_2-4)^2-20\\
(x_1+2)^2+x_2^2-20\\
-x_1\end{pmatrix}\leq ...
0
votes
2answers
519 views
Linear Programming Problem Using the Two-Phase Method
I have been given the following LP problem and asked to use the two phase simplex method to solve it.
I believe there isn't a solution, but would anyone be able to confirm this for me? Thanks.
max
...
0
votes
0answers
15 views
Optimization | Groups with limited spots and priority
As someone at math.stackexchange helped me with this solution, its still not quite right
Problem:
list $L$ can hold $m$ items.
$p_i$ is percent of items from the group than go in $L$ (for i = ...
1
vote
1answer
438 views
A question about the operation research and simplex method
For the simplex method, we need to add slack variables. My question is how to determine how many slack variables should be considered in the LP problem? I don't quite get why in the cases to find out ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
