A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [linear-programming]

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

236 questions
Filter by
Sorted by
Tagged with
2k views

### On the Proof of Fundamental Theorem of Linear Programming.

Having read the link: Why maximum/minimum of linear programming occurs at a vertex? I understand why the optimal solution of any linear programming problem must be on the corner or lies on a face of ...
62 views

### What's the difference between GLPP and LPP

$a)$ Express the following optimization problem as a linear programming problem(LPP): $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$ Hint: you will need to express the ...
294 views

### Proof of binary solution of a linear program with specific structure

When solving instances of the following linear program (LP), I always get an integral (actually binary) solution. Is it just a coincidence or is it possible to prove that there always exists a binary ...
1k views

### Every polyhedron is convex set(proof explanation)

Everything is clear, except one thing, that i didn't get: How do the author of proof make the following jump How exactly he got last inequality?
89 views

### What needs to be linear for the problem to be considered linear?

Harry Altman presented an excellent question in a comment here: What needs to be linear for the problem to be considered linear? So is it enough to a have linear objective function or other ...
1k views

566 views

### Linearization of a non-linear objective function

Consider the optimization problem \begin{align} &\min_{x_1,x_2,y_1, y_2,\delta_1, \delta_2} \delta_1 \max{\{x_1,y_1\}} + \delta_2 \max{\{x_2,y_2\}} \\ &x_1,x_2, y_1,y_2 \in[0,1] \\ &\...
1k views

### Solving a feasible system of linear equations using Linear Programming

I am wondering if one could solve a feasible system of linear equations using a Linear programming approach, instead of standard linear algebra techniques such as gaussian elimination. For instance, ...
202 views

### degeneracy and duality in linear programming

I'm currently learning about linear programming and optimization methods and the most recent subject was duality I'm trying to understand the connection between degeneracy of the primal and ...
322 views

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in \... 1answer 202 views ### minimum possible value of a linear function of n variables Suppose x_1,x_2,\ldots,x_n are unknowons satisfying the constraint a_1x_1 + \cdots + a_nx_n ≥ b, where a_1, \ldots , a_n, b ≥ 0. Then the minimum possible value of the expression c_1x_1 + \... 1answer 1k views ### Reduced cost in the Phase II of the two-phase Simplex? My lecture slides outline how the two-phase simplex works: this table shows the end result of the phase I for the standard-form problem and the auxliary table of the phase I here. I understood until ... 1answer 82 views ### LP problem involving producing assemblies I have to construct an LP problem based on the ff scenario that might be similar to a scenario in another question (in the sense that I felt the need to use mod): The productivities are minutes per ... 0answers 511 views ### Linear Programming with Matrix Game It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ... 1answer 297 views ### Express the constraint “x = 0 or y = 0” in linear programming How to express the constraint "x = 0 or y = 0" in a linear program? Is it possible at all? 1answer 481 views ### Simplex Algorithm: basic solutions - optimal solution [closed] Can someone explain to me the reason why the simplex algorithm proceeds by only considering so-called basic solutions as candidates for the optimal solution to an LP? 1answer 121 views ### How to minimize \| c \mathbf{x} - \mathbf{y}\|_1 without using linear programming? Is there a closed form solution to the minimization problem$$\min_{c \in \mathbb{R}}\left\lVert c \mathbf{x} - \mathbf{y}\right\rVert_1$$where \mathbf{x} = \begin{bmatrix}0 & 1 & \dots &... 1answer 3k views ### Linear Programming Formulation of Traveling Salesman (TSP) in Wikipedia I am confused by Wikipedia's Linear Programming formulation of the Traveling Salesman Problem, in say the objective function. Question: If there are n cities ... 1answer 1k views ### How to determine whether a system of linear inequalities has a positive solution or not? How to determine whether a system of linear inequalities has a positive solution or not? Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms ... 5answers 250 views ### Feasible point of a system of linear inequalities Let P denote (x,y,z)\in \mathbb R^3, which satisfies the inequalities:$$-2x+y+z\leq 4x \geq 1y\geq2 z \geq 3 x-2y+z \leq 1 2x+2y-z \leq 5$$How do I find an interior ... 1answer 3k views ### Absolute values in linear programming Suppose I have an objective function in my LP as follows max |x| Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. |x| =  x^+ + x^- x ... 1answer 112 views ### Deriving a parameter in optimization problem My question: My solution for the part (i) Hopefully my solution is correct. Especially check the budget constraint. If it is correct, then my actual question to you is the second part (i). I ... 2answers 3k views ### Linearizing min function Problem How can I linearize \min(x_1,x_2,x_3) in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows: Objective function is:... 2answers 1k views ### Is the inverse of an invertible totally unimodular matrix also totally unimodular? My question is learned from here. Let me restate it as follows: A unimodular matrix M is a square integer matrix having determinant +1 or −1. A totally unimodular matrix (TU matrix) is a matrix ... 2answers 118 views ### A property of a linear image of the cube Let [0,1]^3 denote the unit cube in \mathbb{R}^3. Let L : \mathbb{R}^3 \to \mathbb{R}^2 be a surjective linear map, and let H := L([0,1]^3) (which is generically a hexagon). Can you provide a ... 1answer 64 views ### Constraints in Vehicle Routing Problem Programming Formulation Problem Background I wished to understand an IP model for the Capacitated Vehicle Routeing problem described below. There are vehicles (of limited capacity) driving around delivering goods to ... 2answers 5k views ### Linear programming: minimizing absolute values and formulate in LP Look for x that minimizes \sum_i| x – a_i| with numbers a_1,\ldots, a_N that are given and formulate this as a LP. I have searched online and found that first of all this \sum_i| x – a_i| ... 2answers 226 views ### Need help defining a Quadratic Programming problem I have an optimization problem which should be solvable with Quadratic Programming: There are n multiplication coefficients c_i for which optimized values are searched. The coefficients are ... 1answer 3k views ### how to check whether feasible solutions exist for linear programming For a linear programming problem, how to decide whether there exists a feasible solution without solving it? For Ax\le B, is there any sufficient and/or necessary condition represented by A and B ... 1answer 559 views ### Tucker's theorem from Farkas lemma I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ... 1answer 692 views ### Simplex method - identity matrix I want to solve the following linear programming problem:$$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$... 2answers 128 views ### Faster algorithms for convex hulls I was interested in the following: Given two polyhedra P_1, P_2 specified in the form:$$ P_1 = \{x : A_1x \le b_1 \}  P_2 = \{x : A_2x \le b_2 \} Whereas x \in R^n and b_1, b_2 ... 1answer 257 views ### Changes in the primal and dual that modify the solutions Suppose we have in standard form an LP: \max cx subject to Ax = b and x \geq 0. Lets' write its dual as well \begin{align*} (P) \max cx &&&&&& (D) \min yb \\ Ax = b &... 0answers 304 views ### What is the role of the recourse variable in stochastic programming? What is the role of recourse variable in stochastic programming? I often see two-stage stochastic programming problems with recourse, written as follows: Stage 1 \begin{equation} \begin{array}{... 2answers 2k views ### linear programming infeasibility, dual & primal relation By the strong duality theorem we know that LP can have 4 possible outcomes: dual and primal are both feasible, dual is unbounded and primal is infeasible, dual is infeasible and primal is unbounded, ... 1answer 193 views ### How to change \min \|Ax-b\|_1 , where x is free, to standard form? I'm trying to find a way to change \min \|Ax-b\|_1 , where x is free, to standard form. I'm extremely rusty on linear algebra, so help would be much appreciated. The textbook gives a method to ... 2answers 257 views ### Simplex algorithm : Which variable will go out of the basis? I want to use the simplex algorithm. At the first step we want to determine which variable will enter the basis. To do that we pick the smallest negative number of the last row of the simplex table. ... 2answers 430 views ### Find the optimal solution without going through the ERO's All I got is that12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$and y_2 = 0 because x_6 is in basis. How do I find y_1 and y_3 without going through the simplex method? I took ... 1answer 188 views ### linearize a sum of linear and piecewise linear functions How can I linearize the following constraint:$$ c_1\max(y + |x| - d_1, 0) + c_2\max(y + |x| - d_2, 0) + e - y \leq 0 \tag{$*$}  where $x,y$ are scalar decision variables, and $c_i, d_i, e \geq 0$? ...
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 ...