# Questions tagged [linear-programming]

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

4,824 questions
Filter by
Sorted by
Tagged with
31 views

• 2,451
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
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
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
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
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
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
31 views

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
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 ...
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
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
41 views

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
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
13 views

1 vote
29 views

• 23
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 ...
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
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
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 ...
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