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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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?
2
votes
1answer
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 ...
2
votes
1answer
1k views

Efficient (time complexity) algorithm for Linear Programming problems

I have an inequality of the form: $$\sum_{i=1}^n a_i\cdot x_i \ge a_0$$ where $a_i\gt 0$ for all $i$. Subject to this and $x_i\ge 0$ for all $i$, I have to minimize the expression: $$\sum_{i=1}^n ...
2
votes
1answer
63 views

How to solve a linear program without any given data? [closed]

What I have done I posted a similar question yesterday (as can be seen here), but nobody could provide a answer up to now and thus I still have difficult time trying to solve this similar problem. ...
2
votes
1answer
65 views

How does one use the 'input/hr' column in the table below in setting up the problem?

I have to set up a linear programming problem corresponding to the following scenario: If my understanding of the problem is correct, I use $mod$: Let $i$ be $A$ or $B$. Let $x$ be amount of raw ...
2
votes
2answers
868 views

How to find the number of possible solutions of LP problems?

Let us assume that we have a linear optimization problem (LP) that has multiple optimal solutions. I would like to know if there is a solver or an algorithm that can provide the number of optimal ...
2
votes
4answers
250 views

Binary variables in time series: integer linear programming

I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series. I have a binary variable $\alpha_t$ for $t \in [0, 24[$. I ...
2
votes
1answer
245 views

How to Solve a Linear Programming Problem in $n$ Dimension Space?

Problem \begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& d^T x = \alpha \\ &0 \le x \le 1. \end{array} The variable is $x\in\Bbb{R}^n$, $\alpha$ and the components of $d$ ...
1
vote
2answers
92 views

check for a compact set

How to prove this $$S = \{(x, y) | Ax + By ≥ c, x ≥ 0, y ≥ 0\}$$ where $A$ is an $m \times n$ matrix, $B$ is a positive semi-definite $m \times m$ matrix and $c \in \Bbb R^m$. The author explicitly ...
1
vote
1answer
62 views

Implications of multiple ways to order four numbers

Consider two sets $A,B$ composed of two real numbers each. These four real numbers are in $[0,1]$. Consider other two real numbers $c\in [0,1]$, $d\in [0,1]$. Assume there exists a way of ...
1
vote
1answer
63 views

Implications of multiple ways to order eight numbers

Consider two sets $A,B$ composed of four real numbers each. These eight real numbers are in $[0,1]$. Consider other four real numbers $c,d,e,f$ each in $[0,1]$, all different between each other. ...
1
vote
2answers
444 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq \begin{pmatrix}0\\...
1
vote
1answer
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] \\ &\...
1
vote
2answers
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, ...
1
vote
1answer
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 ...
1
vote
3answers
322 views

Is an unit-cube polyhedron? What about other platonic solids?

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 \...
1
vote
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 + \...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
-1
votes
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?
6
votes
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 &...
5
votes
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 ...
4
votes
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 ...
4
votes
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 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
4
votes
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 ...
4
votes
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 ...
4
votes
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:...
4
votes
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 ...
4
votes
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 ...
3
votes
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 ...
3
votes
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|$ ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 \}$$...
3
votes
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$ ...
3
votes
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 &...
3
votes
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}{...
3
votes
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, ...
3
votes
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 ...
3
votes
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. ...
2
votes
2answers
430 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_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 ...
2
votes
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$? ...
2
votes
0answers
730 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 ...
2
votes
1answer
3k views

Minimized sum of the distances with street distance

This exercise comes from Bazaraa Linear Programming and Network Flows book : Consider the problem of locating a new machine to an existing layout consisting of four machines. These machines are ...