# Questions tagged [linear-programming]

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

1,444 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
250 views

### Big M constraint question

I have a question regarding using Big M constraints to solve the following problem: Given: $a, b \ge 0$ and integers. $$2a + 5b \le 17\\ a + b \le 5\\ 3a + 6b \le 20$$ For at least two of the ...
325 views

### Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book "...
287 views

### Is simplex method weaker than other methods?

Given linear program: $$\text{min } x_1 - x_2 + 2 x_3$$ s.t.: $$-3x_1 + x_2 + x_3 = 4$$ $$x_1 - x_2 + x_3 = 3$$ $$x_i \geq 0; i = \{1,2,3\}$$ solution by simplex method (with double pass) is ...
84 views

### Higher dimensional Euclidean geometry problem

In my engineering/physics research, I am facing one math problem which I believe should be well established in mathematics... I have a linearly spanned space given by the column vectors of the ...
854 views

### Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
152 views

### Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
53 views

### Linear programming: can someone explain how the time steps work here?

I'm reading a paper, "A Player Selection Heuristic for a Sports League Draft". In it, the authors have come up with a method to assist you in picking players for a fantasy sports league. I'm having ...
54 views

### Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
732 views

### Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
641 views

### Linear programming with (countably) infinitely many variables and finitely many constraints

Is it possible to do linear programming with (countably) infinitely many variables and finitely many constraints? If not, what do you propose? (Example Link): Maximum and minimum of an integral ...
144 views

### Optimizing Rectilinear Distance Traveled

I have a simple pipe network like this (not to scale): I can place a "valve" on any point on that pipe. What the valve does is it permits a certain viscous fluid to fill the pipes. However, because ...
93 views

### Existence of a Linear Optimization Problem

I am working on a linear static optimization problem. I found a solution to the problem. However, I want to formally check the solution existence. I tried some methods but I don't know if it is enough ...
148 views

### Problem generating random vectors with a randomized linear programming with equality constraints (weird clustering)

Summary For simulation problems, I need to be able to generate large numbers of random lists of numbers, say $x_1, x_2, \dots, x_n$ (where $n \approx 1000$), subject constraints similar to what one ...
102 views

### Explicitly solving linear programming problems

Linear programming problems generically involve the use of a repeated algorithm to solve. Is there a reason they can't be solved algebraically/formulaically? Ex: Minimize x1 + x2 + x3.... x1, x2, ...
78 views

### Solving linear equation with some conditions

Consider the equation $y=af+bg+ch$ where $a+b+c=1$ and $a,b,c$ are between 0 and 1. y,f,g,h are vectors with the same size and a,b and c are parameters that must be constant values. How can I solve ...
208 views

### How to visualize duality

In My course of linear programming we are given the definition of a primal/dual problem. However I cannot really get my heard around what it actually is? It helps us in later exercises. Are we ...
73 views

### Linear Program Transformations

I have a Linear Program with constrains of the form: $$a_{11}x_1+a_{12}x_2+\ldots\le 0$$ $$a_{21}x_1+a_{22}x_2+\ldots\le 0$$ $$a_{31}x_1+a_{32}x_2+\ldots\le 0$$ My problem is that if I try to ...
1k views

### Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
580 views

550 views

### Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
226 views

### Linear Optimization Problem - Assign Objects to People

Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values <...
129 views

### Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
95 views

### How can I fairly distribute identical goods bought at different prices amongst customers so that they all pay the same price?

I'm trying to allocate a product bought at different prices to different clients in a fair way. Initially, each of the $n$ client asked for a specific quantity of the product $a_1\ldots a_n$ The ...
457 views

### Sensitivity analysis on non linear problems

First of all, I would like to apologize if this question does not fit into the "soft" category. I am quite a newbie around here, and maybe I can fail to get the feeling of what exactly is a "soft" ...
405 views

### Indicator variable of the sign of a difference in a math program

I am interested in a mathematical program with objective: $\max \sum_{i \in I} x_i$ where $x_i$ is a binary defined variable as follows: $x_i = 1$ if $y_i - A \geq 0$ $x_i = 0$ if $y_i - A < 0$...
228 views

### Smooth Reformulation of NonSmooth Constraints

If I have something like : \begin{align} \min_x \max_i f_i(x) \end{align} I can reformulate this nonsmooth formulation as: $$\min_x z$$ $$z\geq f_i(x)$$ and I have a smooth formulation of the problem. ...
20 views

### LP with binary constraint coefficient matrix

Suppose I have the following LP: \begin{align} \underset{x}{max.} \quad & \sum_i^n c_{i}x_{i} \\ s.t. \quad & \mathbf{A}x \leq b, \; \mathbf{A} \in \{0,1\}^{m \times n}, b \in \mathbb{R}^{m} ...
17 views