Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
49 views

How to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities?

I would like to know how to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities. For example: $$ \left\{ \begin{array}{c} x\ge2 \\ y\...
1
vote
0answers
41 views

Edges Joining Adjacent Vertices

Theorem 3 (Edges joining adjacent vertices; Exercise 2.15, p. 78) Consider the polyhedron $P = \{x \in \mathbb{R}^n \mid a_i'x\geq b_i, i = 1, \dots, m\}$. Suppose that $u$ and $v$ are distinct basic ...
0
votes
0answers
31 views

Are complementary slackness conditions always *sufficient* to obtain the dual solution from an optimal primal solution?

Suppose that I have a guess for the optimal solution $x^\star$ of a linear program $P$. Let $D$ be the dual of $P$. One way to verify optimality of $x^\star$ is through complementary slackness ...
0
votes
1answer
17 views

Dualizing linear optimization problem with difficult indices in summation

I have a question about linear optimization in which I have a double summation and I can't find out how I can convert this to it's dual. This is the problem$:\\$ Maximize $p$ Subject to: $\sum_{i \in ...
0
votes
1answer
27 views

Dualizing linear optimization problem with double summation and dependent indices

I have a question about linear optimization in which I have a double summation and I can't find out how I can convert this to it's dual. This is the problem: \begin{align} \min \quad & \sum_{l=1}^...
0
votes
2answers
26 views

If the polytope is unbounded then there is no optimal solution

Show if true or a counterexample if false a) If the feasible polytope described by the solution space of a linear programming problem is unbounded then there is no optimal solution b) If there are two ...
0
votes
0answers
12 views

Cyclic of Simplex Method

Show that for standard form linear optimization problem with $A\in\mathbb{R}^{m\times n}$ (you may assume that $A$ has full row rank) where $n-m=2$, the simplex method will not cycle, no matter which ...
4
votes
1answer
71 views

Does this matroid invariant have a name?

For a matroid $M$ on $X$ with closure operator $\tau:2^X\to 2^X$ let $c(M)=\min\{|S|:\tau(X\setminus S)\neq X\}$. This is an invariant because if $M$ and $M'$ are isomorphic (i.e. if flats of $M$ are ...
0
votes
1answer
19 views

1-norm reformulation for the following linear program

I have a linear program that I am trying to rewrite in a (possibly not) simpler form, most likely with a 1-norm constraint. The problem is quite simply $\displaystyle\min_{x}{\sum_{i}{x_i}} \quad\text{...
0
votes
1answer
31 views

Is it possible for an inequality constraint to be active at all feasible region in linear programming?

Suppose we have an optimization problem $\min f(x)$ s.t. $ c_1(x) \ge 0$ with one constraint only. Is there a nonlinear constraint (specific example) that is active at all feasible points? what ...
0
votes
0answers
18 views

uniqueness of optimal value when all reduced costs are positive(minimization problem)

I want to prove that if all reduced costs of a basic feasible solution of a minimization problem( linear programming SEF format)are positive, then that Basic feasible solution is the unique optimizer ...
1
vote
1answer
39 views

I don't understand how I can solve the dual of a linear programming model knowing the solution to the primal.

If we know the optimal solution for a primal model how can I find the optimal solution for the dual of that primal model? I heard about complementary slackness which to my understanding is that the ...
2
votes
1answer
33 views

Determine basic feasible solutions in LP

Consider a linear programming problem \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*} Assuming the constraints form a polyhedron, is there any way we can group the ...
0
votes
2answers
34 views

Positve part and negative part of a real number

Let $a$ be a real number . The positive part of $a$, denoted by $a^+$ is given by expression $$a^+ = \text{if } a\geq 0 \text{ then $a$ else } 0$$ The negative part of $a$, denoted by $a^-$ is given ...
0
votes
1answer
26 views

An otherwise linear matrix equation with the presence of a signum function : reference request

Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$ $\pmb{c}$ is a $n\times1$ matrix. $G$ is a $n\times n$ matrix which is also positive definite. matrices $G$ and $c$ are real. $L$ is a $n\...
1
vote
0answers
20 views

Solution space exists, but with introduction of objective function 'linprog' returns no solution

I am trying to solve the problem of the following form: $\min \frac{1}{2} x'Hx + f'x$ subject to, $Ax = b$, and $lb \leq x \leq ub$ I have utilized 'linprog' to check whether the set $Ax = b$, and $lb ...
2
votes
1answer
29 views

Basic optimization problem of n 1 degree variables

Let's say I have the function $f(x_1, x_2, x_3) = ax_1 + bx_2 + cx_3$ and the constraint that $x_1+x_2+x_3=1$ with every $x_1,x_2,x_3\geq0$. I want to find $\operatorname{argmax} f$. It is pretty ...
0
votes
0answers
29 views

LP formulation from simplex tableau

Consider the following simplex tableau for minimization problem: \begin{matrix}z & x_1 & x_2 & x_3 & x_4 & x_5& \text{RHS}\\ 1 & 0 & a & 0 & b & 0 &f\\...
1
vote
1answer
62 views

Solving the LP $\min\{c^Tx\; :\; Ax=b\}$

Let $A\in\Bbb{R}^{m\times n}$, with rank$(A)=m, b\in\Bbb{R}^m, c\in\Bbb{R}^n$. Solve the LP$$\min\{c^Tx\; :\; Ax=b\}$$ and determine when it is unbounded: $\min\{c^Tx\; :\; Ax=b\}=\max\{-b^Ty\; :\; A^...
0
votes
1answer
37 views

Finding the optimal value of a linear program

Consider the LP$$\min c^Tx+b^Ty\\s.t.\;\ Ax\leq b\\\quad \quad A^Ty=-c\\\quad\; \quad y\; \geq 0$$Assume there is a feasible point. Show that there is a (optimal) solution with value $0$. I am not ...
0
votes
0answers
42 views

Maximum flow problem: one arc always has full capacity in the maximum flow does this imply there is a minimal cut through this arc?

I have a maximum flow problem with directed graph G = (V, E) and edge capacities c : E → R≥0 and s, t ∈ V . Of course, there may be more than one flow f that gives the maximum flow value. But now I ...
0
votes
1answer
42 views

Linear programming formulation confusion

I have a silly confusion. For this constraint here, $a_{i1,j1} + a_{i2,j2} ≤ 1$ if $0 < |i1−i2|+|j1−j2| < d$. I understand this constraint but I want to ensure that this encompasses all $i$ ...
1
vote
0answers
14 views

Choosing the index with the strictest constraint and solving the simplex algorithm

Could someone provide an intuitive explanation as to why we choose our pivot element in the simplex algorithm to be the element whose index $\frac {b_i}{a_{ik}}$ is smallest? EDIT: $a_{ik}$ is the ...
0
votes
0answers
15 views

Are these linear programs the same?

Consider the programs $$\forall\underline x\in\mathbb R^n$$ $$\exists a\in\mathbb R$$ $$A\underline x'\leq b\implies B[\underline x,a]'\leq c\wedge a>0$$ and $$\forall\underline x\in\mathbb R^n$$ $$...
1
vote
1answer
36 views

Modeling problem (of Operational Research)

Consider a logistics system consisting of $n$ production sites and $m$ warehouses. For a given product, the monthly production capacity of the production sites is $p_i$ units, with $i = 1,\dots, n$. ...
0
votes
1answer
48 views

Solving a non-linear constrained linear function optimization

Given $k \in \mathbb{N}$, the $k$-vector-norm is defined as the sum of the $k$ largest entries of a vector (largest w.r.t. to absolute value). So if $k=1$, then the $k$-norm is actually the supremum ...
1
vote
1answer
31 views

Efficiently solving system of matrix equations

Suppose I have the two matrix equations: $$A_1 M = C_1$$ $$A_2 M = C_2$$ where $A_1, A_2, C_1,C_2$ are given. I want to know if there is a matrix $M$ with entries in $\{0,1\}$ that satisfies the ...
2
votes
1answer
43 views

Polynomial time for a quadratic equation and linear inequalities?

Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem: \begin{align*} xAx^t = 0, \\ Bx^t = c, \\ x_i \ge 0, \end{align*} ...
0
votes
1answer
37 views

Showing that the linear program is unbounded

Let $A\in\Bbb{R}^{m\times n},\ b\in\Bbb{R}^m, c\in\Bbb{R}^n.$ Consider the linear program:$$\;\;\;\;\qquad \max c^Tx\\ \text{s.t.}\quad Ax\leq b$$Assume that there is a feasible $w$, with $c^Tw\gt 0$ ...
2
votes
2answers
39 views

Multiple variable optimization methods with constraints

This is something I'm doing for a video game so may see some nonsense in the examples I provide. Here's the problem: I want to get a specific amount minerals, to get this minerals I need to refine ore....
0
votes
0answers
20 views

Why we find out the initial feasible solution for transportation problem?

I saw several methods that available to obtain an initial basic feasible solution of a transportation problem. ...
1
vote
1answer
56 views

A question about implementation of Farkas lemma

The Farkas Lemma: Let $A$ be an $m\times n$ matrix, $b\in\mathcal{R}^m$. Then exactly one of the following two assertions is true: (1) There exists an $x\in \mathcal{R}^n$ such that $Ax=b$ and $x\ge0$...
1
vote
1answer
39 views

Linear Programming Basic Solution. Could someone help?

so I am working through the proofs and reading the book "Linear and NonLinear Programming" by Luenberger and wanted to ask for some help. If someone could read the following extract and ...
0
votes
1answer
24 views

How can model this conditional constraint?

I have a known matrix, $S$ of size $N_U\times N_B$. For each row, the elements are sorted in ascending order. I have also defined a binary variable $X$ of size $N_U\times N_B$. I want to formulate a ...
0
votes
0answers
22 views

compute primal variables based on dual answer in linear programming

I have an optimization problem (primal problem) which is solved by the duality theorem. So I have constraints of the dual and its variable's value. it is worth mentioning the problem is linear. how ...
1
vote
0answers
38 views

Can the number of columns be less than the dimension?

I don't see how $k < m$ can possibly occur in part (b). Imagine $X \in R^{n, k}$ describes a matrix for the vectors $x^1$ to $x^K$. $m = \dim( span(S)) \leq \min(n,k)$ Then if $k < m$ in part (b)...
0
votes
0answers
30 views

understanding step in Simplex Algorithm

I am learning the Simplex Algorithm, and currently understand every step except one part. The relevant section from my notes are below. In the second step below, I am not sure why we need to pick $a_{...
0
votes
1answer
32 views

Regression/forecast with an added linear constraint

I am not sure if I am asking on the right place. But given a set of independent variables $X_i$ and the dependent variable $Y_i = f(X_i, b) +c$, how can I estimate the regression equation given a set ...
0
votes
1answer
37 views

How to show that a system of linear equations is not solvable given certain constraints?

Imagine you have the following system of linear equations, $$1 - 3x_1 - x_2 + x_3 + 3x_4 = 0$$ $$1 - x_1 - 5x_2 + 2x_3 + 4x_4 = 0$$ $$1 + x_1 + 2x_2 - x_3 - 2x_4 = 0$$ $$1 + 3x_1 + 4x_2 - 2x_3 - 5x_4 =...
1
vote
1answer
17 views

How to find the $(S ,T)$ for which the objective function $C$ will be maximized?

I have been given the following problem. Maximize $C = S+T$ using duality Subject to the $S + 3T \geq 8$ and $3S + T \geq 8 , S,T \geq 0.$ The duality of this problem is following. Minimize $C' = 8S' ...
0
votes
1answer
43 views

Absolute value problem involving linear programming

John R. has up to $10,000 to invest. His wife suggests investing in two bonds, A and B. Bond A is rather risky with an annual yield of 10%, and bond B is more conservative with a yield of 7%. He ...
2
votes
2answers
76 views

Linear program to model given problem

Here is the problem I'm trying to solve: "A company makes three products, named product A, product B and product C. The company has 4 available workers, and the workers have different rates as ...
1
vote
0answers
39 views

Problem: First determine whether Polyhedron is pointed. If it is find all extreme points of the Polyhedron.

The Polyhedron is defined by these inequalities $x_1 + 2x_2 + 3x_3 \ge 1$ $−x_2 \ge 0$ $x_2 + x_3 \ge 0$ $−x_1 + x_3 \ge −2$ First I want to say you can use the rank condition to determine weather it ...
1
vote
0answers
36 views

Geometric interpretation of linear programs with both inequality and equality constraints

I recently do a homework with linear programming, the standard form as: $$\begin{array}{ll} \text{minimize} &\displaystyle \mathbf{c}^T\mathbf{x}+\mathbf{d}\\ \text{subject to} & \mathbf{A}\...
0
votes
1answer
43 views

Find all the solutions to the system of linear equations

I was given this system of linear equations $x + 2y = 1$ $2x + 4y = 2$ I basically put the system into matrix form and transformed it into rref. \begin{pmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \...
1
vote
0answers
21 views

Adding a variable to a LP: Does the reduced cost completely determine whether the optimal basis and optimal objective function value will change?

On page 203-204 of "Linear Optimization" by Bertsimas and Tsitsiklis, they discuss how introducing a new variable $x_{n+1}$ with corresponding objective function and constraint coefficients (...
0
votes
1answer
38 views

Reference request on how to get a linear optimisation problem from absolute value objective function

Consider the following optimisation problem $$ \min_{\theta\in \mathbb{R}^K} \sum_{l=1}^L |r_l-c'\theta|\\ \text{s.t. } R\theta\leq q $$ where : $r\equiv (r_1,...,r_L)$ is an $L\times 1$ vector of ...
0
votes
0answers
21 views

Active constraints for unbounded Linear programming problem

I want to find which constraints are active for the LP problem under consideration. But the problem turns out to be unbounded. Q. I wish to ask whether it is possible to find which constraints will ...
2
votes
2answers
150 views

Mid-range via minimax

Warning: crossposted at Statistics SE. Given vector ${\rm a} \in \Bbb R^n$, $$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_2^2\end{array} = \...
0
votes
0answers
46 views

Why are spans in Linear Algebra represented using free variables?

I have been doing some refresher work in Khan Academy for Linear Algebra and there was mention of how a column space or any other space can be represented as a fucntion of the free variables and not ...

1
3 4
5
6 7
83