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.

1,441 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
1answer
47 views

Simplex algorithm calculation time exponential rise

I am building an energy-system-model with python/pyomo. It is basically creating an optimization problem (LP) in following form: ...
2
votes
0answers
353 views

Could I have two optimal solutions - linear programming problem?

A company produces two different products. They require two types of ingredients: M and N. The first product require 90 grams of the ingredient M and 10 grams of the ingredient N. The second product ...
2
votes
0answers
47 views

First step of simplex algorithm

I have the following linear program: Maximize $15x + 2y + z$ subject to $$x \le 10 \\ x + y \le 17 \\ 2x + 3 \le 25 \\ y + z \ge 11$$ I created the following Simplex Tableau: ...
2
votes
0answers
122 views

LP-problem simplex with 3 variables

I have this LP-problem which I need to solve using simplex calculations. $$ \max Z = 12x_1 + 18x_2 + 10x_3 $$ when, \begin{align} 2x_1 + 3x_2 + 4x_3 &= 50\\ -x_1 + x_2 + x_3 &= 0\\ -x_2 + \...
2
votes
1answer
239 views

Transforming a linear program into its canonical form for use in the simplex algorithm

A typical example of a LP in my lectures looks like this: From what I've learnt, we are ready to implement the simplex algorithm on this LP, since $x_3, x_4, x_5$ all have positive signs, and so are ...
2
votes
0answers
98 views

How to show that exactly one of the following inequality systems has a solution?

This is from a homework set of my optimization class. Let $A \in \mathbb{R}^{m \times n}$. Show that exactly one of the following inequality systems has a solution: $$ \mathbf{I}: \,\,\,Ax \leq 0,...
2
votes
0answers
59 views

Constraint satisfaction problem (CSP) for inequalities of vectors

I have two vectors $Y= (y_1, y_2, \ldots, y_m)^T$ and $S= (s_1, s_2,\ldots, s_m)^T$, where all entries in $Y$ and $S$ being positive integers. $Y$ is defined by $Y = A + B \cdot X$, where $A$ is a ...
2
votes
0answers
80 views

Linear programming - one-step jump from interior feasible solution to the nearest improving basic feasible solution

Imagine I have a linear programming problem and somehow I am given an initial feasible non-basic solution. Is there a way to easily transform this solution into a basic feasible one that improves (in ...
2
votes
0answers
103 views

an artificial vector in the big M method that produces a BFS

Suppose we have LP maximization where the constraint are put in the form $I {\bf x_B} + B^{-1} N {\bf x_N} = {\bf \overline{b} } $ where : ${\bf \overline{b }} \ngeq 0 $ If we add just one ...
2
votes
0answers
43 views

Solutions of two linear programming

Let $\beta\equiv (\beta_0, \beta_1)\in \mathcal{B}\subset \mathbb{R}^2$ with $\mathcal{B}$ compact. $\beta$ is a known vector of parameters. Let $P_0, P_1, F_0, F_1$ be know parameters, each in $[0,1]...
2
votes
0answers
89 views

Finding a point with maximum distance from a given point in a polyhedron

We are given the polyhedron $X=\{x:Ax\le b,x\ge 0\}$ and the point $y\in X$. We want to find a point $x \in X$ such that $d(x,y)$ is maximized. The function $d(x,y)$ represents the distance between ...
2
votes
0answers
261 views

Benders Decomposition Type of Optimality Cut

In Bender's decomposition we use optimality cuts. An optimality cut is $\pi^T (h-Bx)\leq\phi$ or $b^Ty'+\pi^T (x-\hat x)\leq\phi$, depending on the subproblem. I read in the book that both cuts ...
2
votes
0answers
219 views

Linear optimization with rotation matrix constraint

I have a linear cost function $f(r_{11},r_{12},...r_{33}, t_1, t_2, t_3)$ in terms of the elements of a 4x4 matrix $RT$. It is a rotation cum translation matrix and so the search should obey the ...
2
votes
0answers
39 views

The best approach to tackle the following class of mixed integer nonlinear programming models

I would be thankful if anyone can help me to find the best approach to solve the following MINLP model. In this model, $p_{js}$, $p_{js}$ and $Q$ are parameters. $x_{js}$ is a binary variable and $y_i$...
2
votes
0answers
80 views

Optimizing over union of convex polyhedra

Suppose I have a set of non-empty polyhedra $P_1, \dots, P_n$ , and I wish to optimize a linear function, $c^\top x$, over their union. Is the optimal point of the convex hull of the vertices of the ...
2
votes
0answers
31 views

Derivation of a parameter in optimization problem

My question The solution for first part $$L=(aq+1-a)x1x2+\lambda (y-(a(p1+c)+(1-a)p1)x1-x2p2)$$ As a result after FOCs $$x1=\frac {y}{2(a(p1+c)+(1-a)p1)}$$ $$x2={y\over 2*p2}$$ The solution ...
2
votes
0answers
178 views

Understanding Constraint Matrix in Example Problem

I have found a pretty nice description of the polyhedra model in this paper. They are describing the math behind iterating through for-loops in a program (in last figure below), which forms a ...
2
votes
0answers
128 views

Bott-Duffin-Inverse and linear equation systems

I am interested in checking feasiblity of linear equation systems of the form $$ \begin{split} A x &= b, \\ x &\geq 0 . \end{split} \tag{1} $$ I know that this is basically a linear program ...
2
votes
0answers
79 views

Infinite system of linear equations

During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
2
votes
1answer
528 views

Degenerate feasible basic solution

In Linear programming a degenerate basic feasible solution leads to no increment of the objective function. How , intuitively, the fact that a degenerate solution has at least one variable = 0, it's ...
2
votes
0answers
59 views

A Network Flow Problem Involving Redefined Labeling

Problem We consider a network with $m$ nodes and $n$ directed edges. Suppose we can apply labels $y_r \in \mathbb{R}, \ r=1,2,\cdots,m$ to the nodes in the such way that if there is an edge from $r$ ...
2
votes
0answers
162 views

Two phase simplex when constraint is the same as minimize function

Consider the following linear program: Maximize $Z = x - y$ where $-x+y\ge 1$ and $x\ge 0, y\ge 0$ Add surplus and artificial variables to the constraint: $-x+y-s+a=1$ For phase 1 maximize $W = -...
2
votes
0answers
82 views

Real definition of dual and primal

In optimization, suppose we have a program and we want to minimize something. When we say that a program is dual of the first one what really we mean? It means that if they are feasible and bounded ...
2
votes
0answers
58 views

What is the relationship between basic vectors in Linear Algebra (Vector spaces) and basic variables in the Simplex method for linear programming?

I suppose that basic vectors in Linear Algebra spanning a vector space and basic variables in the Simplex method (Variables that have a non zero value, where the basis represents a corner of the ...
2
votes
0answers
121 views

Integer Programming - Making schedule blocks contiguous?

I am working through this discrete optimization problem that I've defined as an exercise. It is scheduling classes against one classroom. https://github.com/thomasnield/optimized-scheduling-demo I'...
2
votes
0answers
320 views

Linear Programming with Incrementally added constraints

I'm working on a project which involves minimizing a particular objective function with respect to a set of linear constraints (i.e a Linear programming problem). The twist is that, at every time ...
2
votes
0answers
281 views

Solve linear system with restrictions for unknowns

I'd like to know how to find the solution "$x$" to a linear system of equations of the form: $Ax=b$ Where "$A$" is an invertible square matrix containing the coefficients of the system, "$x$" is a ...
2
votes
0answers
285 views

Farkas lemma and duality

In his blog, Terence Tao proves the following this version of Farkas lemma. Propsition.   For $i=1,\dots,m$ let $P_i:{\mathbb R}^n\to{\mathbb R}$ be affine linear functions. Then TFAE ...
2
votes
0answers
50 views

Is Primal path following method conceptually similar to sequential quadratic programming (SQP)?

My teacher teached me about Sequential Quadratic Programming (SQP). It is basically about taking the second order Taylor Series (TS) expansion around your current feasible point, and then finding the ...
2
votes
0answers
52 views

Chicken or egg problem: Which comes first duality or numerical precision in following the central path in LP?

In the interior point method, the path-following version follows the "central path", which is the path that minimizes the Barrier function in a minimization problem $B(x,u) = c^T\cdot x - \mu \cdot \...
2
votes
1answer
46 views

In a polyhedron with vertices, if a vertex has two basic feasible basis, is there a redundant inequality?

We consider a polyhedron $P = \{ x \in \Bbb R^n \mid Ax \leq b\} \neq \emptyset$, $A \in \Bbb R^{m \times n}$, $b \in \Bbb R^m$, $A$ with full column rank. With those hypotheses, we know that $P$ has ...
2
votes
1answer
1k views

Plotting multiple planes with three variables in 3D using MATLAB

I couldn't figure out, how I could plot three different equations with three variables, namely x,y and z in MATLAB or any other Mathematical Softwares. I know that there's a way we could plot multiple ...
2
votes
0answers
61 views

Proving feasibility and unfeasibility

I want to show or prove the following statement: Suppose that some problem $P_M$ is unbounded. If problem $P$ is feasible, then it is unbounded. My gut tells me to prove the contrapositive, namely ...
2
votes
0answers
96 views

Kantorovich translocation of masses 1942 paper

I would appreciate help understanding Kantorovich's 1942 paper on translocation on masses. The English translation can be found here: http://web.eecs.umich.edu/~pettie/matching/Kantorovitch-...
2
votes
0answers
68 views

If ratio test is not unique, can we conclude that the basic feasible solution after pivoting is degenerate?

Assume that you are solving a LP using Simplex method. You reach a point and know that at this point, $x_j$ (one of the decision variables) should leave the basis. So, you perform a ratio test to ...
2
votes
0answers
39 views

Problem with defining a constraint where a weight has to be included

I need to write up a model for a scheduling problem using linear integer programming. This goes well so far but I am stuck with one constraints that I do not know how to write up. I will try to ...
2
votes
0answers
53 views

Is the mapping $f:\mathbb{R^2} \rightarrow \mathbb{R} := \min(x_1,x_2)$ convex?

Is the mapping $f:\mathbb{R^2} \rightarrow \mathbb{R} := \min(x_1,x_2)$ convex ? Definition: A function is said to be convex if it satisfy $f(\lambda x +(1-\lambda)y) \leq\ \lambda f(x) +(1-\...
2
votes
0answers
124 views

Geometric Interpretation of Simultaneous Primal and Dual LP Infeasibility

There are examples of linear programming (LP) problems where both the primal and dual problems are infeasible. For example, \begin{equation} \begin{aligned} &\min_x && x \\ &\ \ \text{...
2
votes
0answers
2k views

Transforming a General Minimization Problem to a Maximization

I am working on a general LP exercise, and am having issues with proving the following: I have a general minimization problem that looks like this: $$\text{Minimum Problem} = \begin{cases} \text{min ...
2
votes
0answers
300 views

Use Farkas' lemma to prove no nonnegative solution exists

Show that the system of equations does not have a nonnegative solution: $\left\{\begin{matrix} x + y + z = 0\\ x - y - 2z = 0\\ x + 2y +3z = 0\\ 2x + 2y + z = 1 \end{matrix}\right.$ I want to ...
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
0answers
62 views

Convert optimization problem to series of equations to solve all variables in O(1)

I have a problem of the form $min\quad |e|,\quad x_1 - x_1',\quad x_2 - x_2',\quad x_3 - x_3'$ $subject\ to\quad \sum x_n <= x_{tot}$ $and\quad (1) \sum f_n(x_n)=K-e$ $and\quad x_1 <= x_1',\...
2
votes
0answers
458 views

Calculate extreme rays of a cone

Let $C=\{(y,z)\in \mathbb R^8:$ $y_1+y_3-z_1=0$, $y_1+y_4-z_2=0$, $y_2+y_3-z_3=0$, $y_2+y_4-z_4=0$, $z_1,z_2,z_3,z_4\geq 0\} $. What is the usual technique to find the extreme rays of $C$? ...
2
votes
0answers
178 views

Bertsimas & Tsitsiklis's Linear Optimization book

I just want to ask a question about the "level" of this book. In the book's preface it is written that the only prerequisite is knowledge of Linear Algebra. Is this book good for undergraduate ...
2
votes
1answer
803 views

Minimisation in Linear Programming

I'm somewhat stuck on an example in Linear Programming. I managed to wrap my head around maximisation for a problem with $\le$ constraints, using both graphical and simplex solutions. However, I have ...
2
votes
1answer
120 views

Linear programming exercise

I want some help for the following exercise I know that the leaving variable is the basic variable associated with the smallest nonnegative ratio with the strictly positive denominator. I can't ...
2
votes
0answers
427 views

Two phase method in linear programming

Suppose following tableau came after one iteration in first phase of a two phase method problem, here $s_1$ is a surplus variable and $s_2$ is a slack variable $w$ is a artificial variable. I tried ...
2
votes
0answers
540 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
2
votes
1answer
90 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
2
votes
0answers
49 views

How to get inequality representation of cone give by generators

To be as specific as possible, I have a subspace $I \subset R^{14}$ of dimension $3$ and an $11\times14$ matrix $A$ with linearly independent rows spanning the orthogonal complement of $I$. I have an ...