Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
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{...
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. ...
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 ...
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 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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{...
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 + \...
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}.

1
2 3 4 5
97