Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
3,561
questions
1
vote
1answer
47 views
Non-Empty Random Set Construction
I am aware any set
$$
\mathbb{S} = \{x\in\mathbb{R}^n | A x \leq b\}
$$
where $A\in\mathbb{R}^{q\times n}$, $q\in \mathbb{R}^q$ is convex, yet there is no guarantee it's also non-empty. Is there ...
1
vote
1answer
26 views
Sensitivity on A Farmer's Case
I have questions, from Bazaraa's book (Linear Programming).
I have calculated point a. This is the optimal table.
Where $x_1$ is wheat, $x_2$ is corn, dan $x_3$ is soybeans.
My question is, what ...
0
votes
2answers
57 views
Linear programming problem and Newtonian mechanics
I am trying to learn Linear Programming. However, I don’t know how to solve the following problem. Maybe you can help, because I am curious to the right approach and solution for this problem. It ...
0
votes
0answers
10 views
linear multivariate constant (known) jacobian optimisation problem with non linear constraints
apologies if I don't give all the information needed I'm a bit out of my depth here.
I have a multivariate optimisation (I think) problem:
y = f(x)
Where x and y are both vectors of the same ...
0
votes
1answer
49 views
Linear programming solution
How to prove a linear program that is feasible and bounded is maximised at one of the basic feasible solution?
0
votes
0answers
74 views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\Phi_g(w):=\sum_{i\...
1
vote
1answer
32 views
My matrices are non-negative,stochastic, irreducible and aperiodic, I want to know whether they always converge in power iteration.
I am working on a problem of SCC graph. The matrix representation of graph will be a square non-negative matrix that is column stochastic, irreducible. I will make it aperiodic by adding a self-loop ...
1
vote
0answers
22 views
Solution is unbounded, optimization problem in Matlab after modification.
The solutions seems to be unbounded even if the array A is changed to [-4 1 5; 4 1 5; 1 1 1];
Anything wrong with syntax. Could not figure out.
Any help.
1
vote
1answer
51 views
How can we solve this simple linear program?
Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,...
0
votes
0answers
37 views
Lifting of a polyhedron
The $l_1$-ball in $\mathbb{R}^d$ is $\{x \in \mathbb{R}^d : \sum_{i=1}^{d} |x_i| \leq 1 \}$.
This is a bounded polyhedron $\mathcal{P}_1$, specified by $2^d$ inequalities as
$\{x \in \mathbb{R}^d :...
1
vote
1answer
35 views
Where can I find a (well-documented) simple solver for linear optimization problems with both equality and inequality constraints?
I need to solve a linear optimization problem subject to both equality and inequality constraints in C++ (using MSVC 15). Mathematically, this can be solved by the simplex algorithm. Since I don't ...
1
vote
0answers
55 views
Uniqueness of Optimal solution of simplex
I have following simplex problem
$$\begin{array}{ll}\text{minimize} & z= -2x_1 - 3x_2 -6x_3\\\\ \text{subject to} &2x_1+x_2+x_3\le5\\ & 3x_2+2x_3\le6\\ & x_1, x_2, x_3 \geq 0\end{...
2
votes
0answers
25 views
Structure of an Optimal Solution to a Fractional Packing Problem
Packing LP
We have the following optimization problem:
$$ \max_{x_{ij}} x_{ij} c_{ij}$$
s.t. $$(i)\forall j\mbox{ }\sum_{i} x_{ij} \leq \beta_j$$
$$(ii)\forall i\mbox{ }\sum_{j} x_{ij} D_{ij} \leq 1$...
3
votes
1answer
66 views
Proving optimal solution for Linear Programming
Suppose we have a standard optimization problem. $A'$ is an optimal solution to the problem. If we add a constraint to our original optimization problem, and $A'$ satisfies the new constraint, then is ...
1
vote
2answers
45 views
Is the solution to Mean Squared Error also the one to Mean Absolute Error?
When I was dealing with optimization problem and deciding whether to minimize MSE or MAE, I had the following question: Is the solution to Mean Squared Error also the one to Mean Absolute Error? If ...
1
vote
1answer
65 views
Maximum number of vertices a polyhedron can have?
During my linear programming class we saw this theorem:
Theorem: Let $A \in \mathbb{R}^{m \times n}$ where $\operatorname{rank}{(A)} = m \leq n $ and let $b \in \mathbb{R}^m-\{\bar{0}\}.$ Then ...
0
votes
0answers
30 views
Dual linear program in electric circuit
There are explanations of dual linear programs in terms of economics like Farmer example on Wikipedia.
In a book Ten lectures on statistical and structural pattern recognition I've found a real-world ...
1
vote
0answers
31 views
How to identify endpoints in convex polytopes with more variables than constraints?
For example, consider the set
$$S_1 = \left\{ (x_1, x_2, x_3) \in \mathbb{R}_{\geq 0}^3 : x_1 + x_2 + x_3 \leq 2 \right\}$$
Adding slack variables, we obtain
$$x_1 +x_2 +x_3 +x_s = 2$$
If we had $...
0
votes
0answers
14 views
How to find feasible points without optimization
Find a feasible points from the following set of inequalities by using dual simplex method:
$$2x_1+3x_2 \le12$$
$$-3x_1+2x_2\le- 4$$
$$3x_1 -5x_2\le2$$
$$x_1 ~~\text{is in }~\mathbb R,~ x_2\ge0$$
I'...
0
votes
2answers
42 views
How can I start looking for extreme points in convex polytopes?
Consider $S \subset \mathbb{R^2}$ a set such that $\forall (x_1,x_2) \in S$ :
$ 2x_1+3x_2 \leq 6 $
$-2x_1+ x_2 \leq 2$
$x_1 \geq 0 , x_2 \geq 0$
How can I find extreme points of $S$? What is a ...
0
votes
2answers
52 views
How to prove that $S=\{(x,y) \in \mathbb{R}^2 : x+y \leq 2 \}$ has no extreme points?
Let
$$S := \left\{ (x,y) \in \mathbb{R}^2 : x + y \leq 2 \right\}$$
Definition: A point $x \in S$ is extreme if it cannot be written as a convex combination of other elements of $S$.
I started ...
1
vote
0answers
45 views
Coding for Applied Linear Algebra Course
This is totally embarrassing but I have never coded, much less programmed, anything in my life and suddenly my applied linear algebra course requires us to write a code for a project.
The project ...
0
votes
2answers
36 views
Can Bayesian Optimization be used in lieu of LP, QP, or MIP?
Is it possible to use Bayesian Optimization as a generic solver for traditional constrained optimization problems like LP, QP, MIP, etc...or it is it limited in scope to Hyperparameter search and auto-...
0
votes
2answers
30 views
What linear program characterizes non-infinitesimal perturbations of a linear program?
Suppose that I possess the solution to
$$
\max_x\ c^\top x \textrm{ subject to } Ax \le b_1.
$$
How can I use this to more efficiently solve
$$
\max_x\ c^\top x \textrm{ subject to } Ax \le b_2?
$$
...
2
votes
2answers
98 views
Simplex Method gives multiple, unbounded solutions but Graphical Method gives unique soution
I'm taking an undergraduate course on Linear Programming and we were asked to solve the following problem using the Simplex Method:$$\max:~Z=3x+2y\\\text{subject to}\begin{cases}x+y\le20\\0\le x\le15\\...
1
vote
1answer
74 views
Use $x\ge 0 \implies y = 1$ and $x<0 \implies y = 0$ into a linear programming solver
For a binary variable $y$ and another decision variable $x$, $x$ being integer, I want to be able to use the following two non-linear constraints into a linear solver:
\begin{align}
x\ge 0 \...
0
votes
1answer
47 views
What is the proof for boundedness of the following LP problem?
\begin{array}{ll}
\text{maximize} & Ax + By \\
\text{subject to}& Cz + Dw = 1 \\
& A’x + B’y \le C’z + D’w \\
&x, y, z, w \ge 0.
\end{array}
where A, B, C, D, A’, B’, C’, D’ are ...
0
votes
0answers
23 views
What is the meaning of $k$ in this paragraph from “The Application of Linear Programming to Team Decision Problems” by Radner?
The attached paragraph is from "The Application of Linear Programming to Team Decision
Problems."
I do not understand how the profit depends on the capital limit $k$ (whose definition is also ...
0
votes
0answers
75 views
Linear programming using MATLAB
I'm currently trying to solve a problem. According to some people I know it's a linear programming problem, however, I've not had the course just yet.
Situation:
At my warehouse we get different ...
0
votes
0answers
23 views
Rewrite linear optimisation problem in canonical form
Preliminary notation: Consider a finite set $\mathcal{Y}\equiv \{1,...,L\}$ and a function $u:\mathcal{Y}\rightarrow \mathbb{R}$. Let $\Delta(\mathcal{Y})$ be the set of probability distributions over ...
0
votes
1answer
37 views
How to add multiple cuts as lazy constraints
I have a minimization problem where I implement Benders decomposition and add my cuts as lazy constraints. I am able to add multiple cuts at each iteration since the sub problem is seperable. Also, I ...
0
votes
0answers
20 views
Transportation problem in LPP
How to prove that in a Transportation Problem there will be even no of cells?
It is quite obvious thing, I can understand easily by looking into a probelm and by solving it.
But is there any proof of ...
2
votes
1answer
45 views
Right-inverse approximation in Frobenius Norm
Let $A \in \mathbb{R}^{m\times n}$, with $m \geq n$, be a matrix of rank $r$, and suppose we have a SVD decomposition $A = U\Sigma V^t$.
We define the pseudo-inverse of $A$ as $A^{\dagger} := V\...
0
votes
1answer
45 views
Finding the number of all possible pair products less than the product of two given numbers
Suppose the are two lists X,Y each has numbers from 1 to 110 , we are given given a element from X,Y each, then we have to find number of possible pair of factors from X,Y so that the product of each ...
1
vote
0answers
86 views
Writing the dual of a linear minimisation problem
I am trying to write down the dual of a linear minimisation problem and I would like your help to double check whether I'm doing it right. I'm following the instruction here .
The original ...
0
votes
1answer
17 views
Method of determining the correct side
In Linear Programming, we use the “origin side” method to determine which side is the “>” side of the straight line $f(x, y) = 0$.
I know it is NOT necessary true that $f(x, y) > 0$ is always on ...
0
votes
1answer
33 views
How does row operation work in the simplex algorithm?
Reading through the wikipedia page for the simplex algorithm and I can't figure out how the row operation they have as an example works...
$$
\text{Minimize} \\
Z = -2x - 3y - 4z \\
\text{Subject To} ...
2
votes
0answers
23 views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
1
vote
1answer
45 views
Travelling salesman problem visiting different nodes different times [closed]
Hi I am trying to solve a more complicated travelling salesman problem (shortest path visiting all nodes in a directed graph), where
(1) I need to revisit different nodes for different times,
(2) I ...
2
votes
1answer
54 views
Linearize a constraint
I have intermediate knowledge of optimization and mathematical modeling
I have this constraint. I know how to model it with integers (which leads to a mixed-integer linear program). However,I was ...
1
vote
0answers
121 views
Basic solution and linearly independent columns - exercise 2.3 Bertsimas and Tsitsiklis
I am trying to solve exercise 2.3 of the book "Introduction to linear optimization" by Bertsimas and Tsitsiklis, which states:
$\textbf{
Exercise 2.3 (Basic feasible solutions in standard form ...
3
votes
1answer
82 views
Determining if a Vector is a member of a Convex Hull
Edit: Here is how the following sets are created:
$S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear ...
1
vote
0answers
34 views
Why are the variables in the dual linear program the shadow price?
Good evening.
In lineary optimization, we have primal and corresponding dual programs. It is often said that the variables in the dual program can be interpreted as the shadow price for the ...
2
votes
1answer
30 views
How can I adjust the coefficients in the constraints of a Linear Programming problem with no objective function until I get a solution?
I have a system of linear equations that I need a solution for that is strictly positive. I have 4 solutions and 4 unknowns, and the solution I obtain for my current system involves negative numbers.
...
3
votes
1answer
77 views
Feasibility region of LP
Consider the problem
$$
\text{ Find } y \text{ s.t. } \\
\exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx
$$
where $y$ is a $2\times 1$ vector of unknowns, $x$ is a $10\...
2
votes
0answers
31 views
Inverting Linear System of Inequalities
I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities:
$$m\leq m' \leq p+m$$
$$m \leq m'-z' \leq p+m$$
$$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$
(The last one is an equality)....
1
vote
1answer
153 views
Simplex method can't solve assignment problem?
The problem:
I am trying to solve http://acm.timus.ru/problem.aspx?space=1&num=1076 , it's an online judge for programming problems. The problem could be solved by a simple application of an ...
0
votes
0answers
17 views
Runtime of source with varying resource consumption
This question is regarding a simple problem, which can be posed for different physical situations. I am posing for a particular physical situation, but the idea is to exposit the general mathematical ...
2
votes
1answer
105 views
Linear Programming and graphing (Mathematics in thw Modern World)
I need help with the #1 question. linear Programming is applied.
1. Consider the recipes below:
...
0
votes
0answers
30 views
Why do the conditions have to be smaller than in linear programming?
The basic problem in linear programming is:
max $ c^Tx $
$ Ax \leq b $
$ x \geq 0 $
But why does the condition have to $ \leq $ instead of $ \geq $ ? In fact, when considering the dual problem, it ...
