Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,824
questions
0
votes
0
answers
31
views
Smooth approximation of a five phase linear function
I am looking for a smooth (continuous differentiable) approximation of the following five-phased linear function:
$$
P(U, R, P_r) = \begin{cases}
R(U_{\max} - U) + R(U_{up} - U_{\max}) + P_r; & U \...
0
votes
0
answers
22
views
Derivative of shadow price in LP objective coefficient
Consider the standard LP with value function
\begin{equation}
\Omega(\mathbf{A}, \mathbf{b}, \mathbf{c}) = \max_{\mathbf{x}} \left\{\mathbf{c} \cdot \mathbf{x} \,|\, \mathbf{A}\mathbf{x} \leq \...
- 49
0
votes
1
answer
61
views
Minimize $\sum_{e \in E} w(e)x_e$
Is the following formulation of the un-directed minimum spanning tree (MST) aproblem? Minimize $\sum_{e \in E} w(e)x_e$. Subject to:
$\sum_{e \in \delta(S)} x_e \geq 1$ for all $S \subset V, S \neq \...
- 9
2
votes
0
answers
38
views
How to determine if a constraint is redundant in a linear programming problem
my TA told me that a constraint is redundant iff it is a linear combination of the other constraints. Let's consider these constraints:
$2x_1 + x_2 \leq 4$
$-2x_1 + x_2 \leq 2$
$x_1 - x_2 \leq 1$
...
- 191
0
votes
1
answer
21
views
Linear programming: Check if this base is feasible
I have an LP:
$$
\max z: 5x1 + 12x2 +4x3
$$
s.t
$$ x1 + 2x2 +x3 + x4 = 10$$
$$2x1 + -2x2 -x3 = 2 $$
I want to check some bases if they are feasible. For $B=(P_1 P_2)$ I did:
$B = \begin{...
- 717
1
vote
0
answers
77
views
Proving that $c^Tx_B<c^T\hat x_\hat B$ holds.
I have this problem: Given the linear optimization problem $\max\{c^Tx|x\in P\}$, where $P\subset \mathbb{R}^n$ is a polyhedron. Further, let $x_B$ be a non-degenerate basis solution to the basis B. ...
- 55
0
votes
1
answer
35
views
How to approach a LP problem with Upper bounds
I need to solve the following problem:
$$\max: x_1+12x_2+65x_3; $$
$$x_2+4x_3 \leq 200;$$
$$x_1+10x_2+60x_3 \leq 750; $$
$$x_1,x_2,x_3 \leq 50 $$
To solve it efficiently by hand, I have tried to make ...
- 11
0
votes
0
answers
24
views
Alternate optimal can be unbounded
Can it happen that at the optimal simplex table for a maximization problme, we have reduced cost of one of the nonbasic variable as 0, but no entry in its corresponding column at the optimum is ...
- 2,605
0
votes
0
answers
17
views
Largest centered $(n-1)$-ball in an $n$-dim polyhedral complex
Let $P :=\bigcup_{i=1}^k P_i$ be a polyhedral complex in $\mathbf{R}^n$ composed of $\{P_1, P_2 \cdots P_k\}$. Note that $P$ can be non-convex. Let $T$ denote the boundary of $P$. We are interested in ...
- 121
2
votes
2
answers
72
views
Optimization problem involving the sum of reciprocals of variables
I'm trying to solve an optimization problem involving reciprocals.
The problem has the following simple form. Can this form be transformed into a problem form that commercial optimization solvers can ...
- 21
0
votes
1
answer
63
views
Triangles in a graph via LP
I have a linear program and I can't formulate the objective function and constraints.
For a graph $G = (V, E)$ we may select a set $S$ of vertices of $V$. Each vertex carries a cost $c_v > 0$ if it ...
1
vote
1
answer
27
views
Seperating Spanning Tree inequalities and equivalence to rank function of the cycle matroid
The motivation of this post is to answer the question
How can I decide for a given graph $G = (V,E)$ and $x \in \mathbb{R}^E$ whether $\sum_{e \in E[X]}x_e \leq |X| -1$ for all non-empty $X \subseteq ...
- 179
0
votes
0
answers
20
views
Unit vectors with the same sized pairwise (non-zero) angle in Euclidian spaces $\mathbb{R}^n$ [duplicate]
Consider 3 unit vectors on $\mathbb{R}^2$. Then for them to have pairwise angles of the same size, the unique non-trivial solution is $\theta=\frac{2}{3}\pi$.
In the Euclidean space $\mathbb{R}^3$, ...
- 1
-1
votes
0
answers
16
views
Finding optimal argument and optimal value of a minimalization expression
I have an expression:
min $||A^{T}x||_2$ with constraint: $||x||_2 = 1$
For this expression I am supposed to find optimal argument and optimal value and explain if it is convex or not.
I dont know how ...
- 1
0
votes
1
answer
13
views
Least square objective function as a convex function
Given the least square problem $min ||Ax-y||_{2}^{2}$ for a matrix $A \in \mathbb{R}^{m\times n}$ and vector $y \in \mathbb{R}^m$.
Show that the objective function $f(x) = ||Ax-y||_{2}^{2}$ is convex ...
0
votes
2
answers
78
views
How to apply complementary slackness
Given the primal
$$\max z= 5x_1-4x_2+3x_3$$
subject to
$2x_1+x_2-6x_3=20$
$ 6x_1+5x_2+10x_3\leq 76$
$8x_1-3x_2+6x_3\geq 50$
with $x_1\in \mathbb{R}, x_2\geq 0,x_3\leq 0$.
The question is to construct ...
- 2,605
1
vote
1
answer
26
views
Dot product of vectors with matrix transformation
I have two vectors $a,b \in \mathbb{R}^3$ and use the dot product to calculate the angle $a\bullet b=\lambda$. But I need to transform the vector $\vec a$ with the matrix A. Is there a way to find a ...
- 13
0
votes
0
answers
20
views
Linear complementary problem
for the linear complementary problem
$(Aw-b)^{T}(w-f)=0$, $Aw-b \geq 0$, $w-f \geq 0$ .. (1)
Further,
$w \in \mathbb{R}^{N-1}$ , $w \geq f$ and $K(w) = min_{ v \geq f} K(v)$
whereby $K(v) = \frac{1}{2}...
- 481
2
votes
1
answer
43
views
Symmetric optimization problem
Consider a linear or non-linear optimization problem of the form:
$$\min x_1$$
$$x_1 \ge x_2 \ge x_3$$
$$f_1(x_1,x_2,x_3,x_{12},x_{13},x_{23},x_{123}) \ge 0$$
$$\ldots$$
$$f_n(x_1,x_2,x_3,x_{12},x_{13}...
- 2,451
0
votes
0
answers
24
views
Relationship between 2 maximizing problem (linear programming)
Say problem one I have a linear programming problem of $f(x)$ maps $\mathbb{R}^n \to \mathbb{R}$ subject to constraint $C$.
I also have problem two, and it is to maximize $r$ and that $f(x)\ge r$ and ...
- 21
1
vote
1
answer
90
views
"Solving" a system of linear inequalities for the first variable
I have some non-negative real variables $x_1, \ldots ,x_n$ and non-negative real constants $a_{i,j}, 1 \le i \le n, 1 \le j \le n$, such that $a_{i,j} = 0 \iff i > j+1$, and other positive real ...
- 2,451
3
votes
1
answer
43
views
"One-Sided Hungarian" or "Hungarian for Roommate Problem"
The Hungarian algorithm is a solution to a two-sided matching problem. There are similar "one-sided" matching problems, such as the roommates problem. Like the Hungarian, roommates need to ...
- 240
1
vote
1
answer
69
views
Using linear or integer programming to find cardinality
I just learnt the basics of linear and integer programming, i know that for a given property X, it is sometimes possible to rewrite the question "What is the maximal size of a set having property ...
- 31
1
vote
1
answer
78
views
Tractability of linear programming
Consider a linear program
$$
\max_{x} c^\top x\\
\text{s.t. } Ax \leq b\\
\text{and } x\geq 0
$$
I have been asked to comment on the "computational tractability" of such a program.
I am ...
- 118
7
votes
1
answer
77
views
Multidimensional Assignment: Is it really NP-Hard? Why? What's the Intuition?
I recently learned about the multidimensional version of the assignment problem (the 1:1
version was studied in the Kuhn-Murkes Hungarian algorithm for bipartite graphs).
The article I was reading was ...
- 240
0
votes
2
answers
31
views
Hungarian Extension: Additive Costs, Non-Additive Benefits
I have a problem that's adjacent to the Hungarian algorithm, but not identical. Suppose I have $N$ workers and $N$ jobs, and I want to develop a matching for all $N$ on both sides. There are $N!$ ways ...
- 240
0
votes
0
answers
8
views
Arbitrary bounds in interior point methods
I want to implement a simple interior point solver for linear programs that I intent to use later. I read the corresponding chapter of several references (i.e Numerical Optimization) and all of them ...
0
votes
0
answers
60
views
Identifying geometric shapes in matrix using algebraic constraints
I'm currently studying topology for my thesis. The problem I'm having now is identifying geometric shapes (e.g. rectangles) in a grid (see image). At this point I'm trying to keep it as mathematical ...
- 1
1
vote
2
answers
35
views
How to find the basis of a transformation matrix?
I need help with b. Lets call the column vectors of the transformation matrix $w_1, w_2, w_3$. I can already see that $w_3 = \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix}$ or simply the norm. But I am ...
- 195
1
vote
0
answers
41
views
Sum equal to product in $\mathbb{Z}/n\mathbb{Z}$ under constraints
I need to solve the following problem.
Let $A=\{a_0,a_1,a_2,\cdots,a_k\}$
Find $a_i$ such that:
$|A|\geq 3$
$a_i\in \mathbb{N}$ and $a_i\in [32,127]$
$p=\sum_i a_i$ is prime
and
$\sum_i a_i = \prod_i ...
- 304
1
vote
0
answers
33
views
Existence of a positive solution $x\geq 0$ for $Ax = b$ for a specific $A$ and an arbitrary, positive $b.$
Let $P$ be a convex polytope in $\mathbb{R}^m$ with $n$ vertices $x_1,x_2,\dots x_n.$ Define the Pareto boundary $\mathcal{P}$ of $P$ as the part of the boundary of $P$ consisting of points that are ...
- 12.5k
0
votes
1
answer
90
views
How to make this mathematical modeling linear?
The problem I'm dealing with has the objective to minimize the amount of people we need to hire. We have 14 contracts with 14 companies, each of which have shared with us the amount of workers that ...
- 362
0
votes
1
answer
32
views
Why can certain variables be left out of an Objective function in Mathematical Programming?
I have an objective function that has the form:
\begin{equation}
\min \qquad \sum_{i} \omega_{i}x_{i}q_{i}
\end{equation}
Where $\omega_{i}$ is the weight of variable $i$, $x$ is the decision ...
0
votes
1
answer
32
views
Using the method of feasible regions, solve the linear program
Minimise $\;z=2a+b\;$ subject to
$a\leqslant10$
$2a+5b\leqslant60$
$a+b\leqslant18$
$3a+b\leqslant44$
$a\geqslant0$, $\;\;b\geqslant0$
Usually I would plug the extreme points of the feasible region ...
- 119
0
votes
0
answers
22
views
Primal constraints satisfaction
Given $\min_x f(x)$ subject to $g(x) = 0$, we write the Lagrangian as $\mathcal{L}(x,\lambda) = f(x) + \lambda g(x)$ and the dual as $g(\lambda) = \min_x \mathcal{L}(x,\lambda)$.
Let $x^* = \arg\min_x ...
- 269
0
votes
1
answer
32
views
How to generate $\mathbb{R}^3$ vectors with a constraint on the sum?
I would like to solve a kind of linear equation with constraints. I think the linprog function of scipy could be a good choice but I have some difficulties to translate my problem and use this routine....
- 101
0
votes
0
answers
22
views
Computing the integral of a linear function over a polyhedron
I am currently looking for a way to compute the integral of an n-dimensional linear function over a convex region in the shape of an n-vertex polyhedron. So far I have tried the R package ...
- 17
1
vote
0
answers
13
views
Relationship between vertices in standard form and basic feasible solutions in canonical form LP
Please check if my thoughts is correct.
Let we have the following linear programing problem
$$max\, c^Tx$$
$$Ax\leq b,$$
$$x\geq 0,$$
where $A$ is a matrix with $m$ rows and $n$ columns, $x\in\mathbb{...
- 69
0
votes
0
answers
33
views
Simplex Algorithms: Identifying simplex method for a question.
I am just getting started with the basics of simplex algorithms so I don't know much about them except the calculations (and that's all I am focusing on for now). I have studied Big M, 2 Phase, Dual ...
-1
votes
1
answer
79
views
Maximum the distance between multiple vectors for a linear system?
If you have multiple matrices $A_1, A_2, A_3, A_4, \dots A_n$
All these matrices are going to be multiply by a vector $x$
$$A_ix$$
The product of $A_ix$ can we call $b_i$
$$b_i = A_ix$$
The goal of ...
- 2,724
0
votes
1
answer
43
views
LP Duality. What is the correct dual to this linear program?
Suppose a linear program that is defined as follows with decision variables $ w, x, y, z$ and parameters $a, b, c_j, d_i$.
$\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$
$s.t.$
$x_{i} \geq w + \...
- 45
1
vote
0
answers
29
views
What is the complexity of checking whether two polytopes have a common vertex
Let $C_k \in \mathbb{R}^n$ for $k \in \{1, ..., m\}$ and $C_0^1, C_0^2 \in \mathbb{R}^n$. Consider the polytopes
$$ \mathcal{P}_1 = \{x | \max_{k} \|x - C_k\|^2 - r_k^2 - \|x - C_0^1\|^2 \leq -R_1^2\}$...
- 1,143
0
votes
0
answers
26
views
Attempting to convert a linear programming problem to its standard form
I was given this (LP):
$$
\min\ -x_1 + x_2
\\\\
\text{s.t.}
\\\\
x_1 \le 1 \\
-x_1 + x_2 \ge 1\\
x_2 \ge 0
$$
and this is my attempt to transform it in standard form:
$$
\min\ x_2 - x_5 + x_6
\\\\
\...
- 23
-1
votes
2
answers
29
views
Conditional statement in mixed integer linear programming
I have been trying to enforce the following conditional statement in a MILP:
If $X_1 + 2(X_2 + X_3) = 4$, then $X_4 = 1$.
where $X_1, X_2, X_3, X_4$ are binary.
How can I write this in conventional ...
0
votes
4
answers
58
views
How this norm is converted to a linear programming problem
I came across this problem in control systems and I would like to know how minimizing the norm is converted to a linear programming problem. The optimization problem seeks to minimize the Taxicab norm ...
- 899
0
votes
0
answers
23
views
How to prove strong duality in linear programming using minimax theorem?
Let me provide the details of my request step-by-step.
In the further description, I consider finite $n \in \mathbb{N}$ and $m \in \mathbb{N}$ and $\mathbb{R}$ without $\infty$ and $-\infty$. Set $\...
- 487
0
votes
0
answers
27
views
Do i have to add an auxiliary variable when adding a new equality constraint at a LP?
For example I have the following problem:
\begin{align}
&\textrm{min z} = -2x_1 -x_2 +x_3 \\
&\textrm{s.t.} \\
& \qquad x_1 +2x_2 +x_3 \leq 8 \\
& \\
&\quad -x_1 +x_2 -2x_3 \leq 4 ...
0
votes
0
answers
44
views
How does the Simplex method actually work?
I learned about the simplex method, how to pivot by hand before commercial grade solvers were introduced. And I’m still a little foggy on what slack variables and objectives are actually doing.
My ...
- 193
0
votes
0
answers
11
views
Determine score matches from standings information
In the world cup group stage there are 4 teams per group. Each team needs to play against all 3 other teams, for a total of 6 matches. After the matches are done, the results are recorded in a table ...
- 13
0
votes
0
answers
10
views
Linear Programming
How to find the recession directions of a polyhedral ?
Is (2/3,1/3) a recession direction of ?
X={(x1,x2) : x1+x2 > 2, x1 - x2<=0, x1 - 4x2 <=2}.
