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
1
vote
1answer
68 views

Maximum number of vertices a polyhedron can have?

During my linear programming class we saw this theorem: Theorem: Let $A \in \mathbb{R}^{m \times n}$ where $\operatorname{rank}{(A)} = m \leq n $ and let $b \in \mathbb{R}^m-\{\bar{0}\}.$ Then ...
0
votes
0answers
30 views

Dual linear program in electric circuit

There are explanations of dual linear programs in terms of economics like Farmer example on Wikipedia. In a book Ten lectures on statistical and structural pattern recognition I've found a real-world ...
1
vote
0answers
31 views

How to identify endpoints in convex polytopes with more variables than constraints?

For example, consider the set $$S_1 = \left\{ (x_1, x_2, x_3) \in \mathbb{R}_{\geq 0}^3 : x_1 + x_2 + x_3 \leq 2 \right\}$$ Adding slack variables, we obtain $$x_1 +x_2 +x_3 +x_s = 2$$ If we had $...
0
votes
0answers
14 views

How to find feasible points without optimization

Find a feasible points from the following set of inequalities by using dual simplex method: $$2x_1+3x_2 \le12$$ $$-3x_1+2x_2\le- 4$$ $$3x_1 -5x_2\le2$$ $$x_1 ~~\text{is in }~\mathbb R,~ x_2\ge0$$ I'...
0
votes
2answers
46 views

How can I start looking for extreme points in convex polytopes?

Consider $S \subset \mathbb{R^2}$ a set such that $\forall (x_1,x_2) \in S$ : $ 2x_1+3x_2 \leq 6 $ $-2x_1+ x_2 \leq 2$ $x_1 \geq 0 , x_2 \geq 0$ How can I find extreme points of $S$? What is a ...
0
votes
2answers
54 views

How to prove that $S=\{(x,y) \in \mathbb{R}^2 : x+y \leq 2 \}$ has no extreme points?

Let $$S := \left\{ (x,y) \in \mathbb{R}^2 : x + y \leq 2 \right\}$$ Definition: A point $x \in S$ is extreme if it cannot be written as a convex combination of other elements of $S$. I started ...
1
vote
0answers
45 views

Coding for Applied Linear Algebra Course

This is totally embarrassing but I have never coded, much less programmed, anything in my life and suddenly my applied linear algebra course requires us to write a code for a project. The project ...
0
votes
2answers
37 views

Can Bayesian Optimization be used in lieu of LP, QP, or MIP?

Is it possible to use Bayesian Optimization as a generic solver for traditional constrained optimization problems like LP, QP, MIP, etc...or it is it limited in scope to Hyperparameter search and auto-...
0
votes
2answers
31 views

What linear program characterizes non-infinitesimal perturbations of a linear program?

Suppose that I possess the solution to $$ \max_x\ c^\top x \textrm{ subject to } Ax \le b_1. $$ How can I use this to more efficiently solve $$ \max_x\ c^\top x \textrm{ subject to } Ax \le b_2? $$ ...
2
votes
2answers
111 views

Simplex Method gives multiple, unbounded solutions but Graphical Method gives unique soution

I'm taking an undergraduate course on Linear Programming and we were asked to solve the following problem using the Simplex Method:$$\max:~Z=3x+2y\\\text{subject to}\begin{cases}x+y\le20\\0\le x\le15\\...
1
vote
1answer
74 views

Use $x\ge 0 \implies y = 1$ and $x<0 \implies y = 0$ into a linear programming solver

For a binary variable $y$ and another decision variable $x$, $x$ being integer, I want to be able to use the following two non-linear constraints into a linear solver: \begin{align} x\ge 0 \...
0
votes
1answer
48 views

What is the proof for boundedness of the following LP problem?

\begin{array}{ll} \text{maximize} & Ax + By \\ \text{subject to}& Cz + Dw = 1 \\ & A’x + B’y \le C’z + D’w \\ &x, y, z, w \ge 0. \end{array} where A, B, C, D, A’, B’, C’, D’ are ...
0
votes
0answers
23 views

What is the meaning of $k$ in this paragraph from “The Application of Linear Programming to Team Decision Problems” by Radner?

The attached paragraph is from "The Application of Linear Programming to Team Decision Problems." I do not understand how the profit depends on the capital limit $k$ (whose definition is also ...
0
votes
0answers
83 views

Linear programming using MATLAB

I'm currently trying to solve a problem. According to some people I know it's a linear programming problem, however, I've not had the course just yet. Situation: At my warehouse we get different ...
0
votes
0answers
23 views

Rewrite linear optimisation problem in canonical form

Preliminary notation: Consider a finite set $\mathcal{Y}\equiv \{1,...,L\}$ and a function $u:\mathcal{Y}\rightarrow \mathbb{R}$. Let $\Delta(\mathcal{Y})$ be the set of probability distributions over ...
0
votes
1answer
37 views

How to add multiple cuts as lazy constraints

I have a minimization problem where I implement Benders decomposition and add my cuts as lazy constraints. I am able to add multiple cuts at each iteration since the sub problem is seperable. Also, I ...
0
votes
0answers
21 views

Transportation problem in LPP

How to prove that in a Transportation Problem there will be even no of cells? It is quite obvious thing, I can understand easily by looking into a probelm and by solving it. But is there any proof of ...
2
votes
1answer
50 views

Right-inverse approximation in Frobenius Norm

Let $A \in \mathbb{R}^{m\times n}$, with $m \geq n$, be a matrix of rank $r$, and suppose we have a SVD decomposition $A = U\Sigma V^t$. We define the pseudo-inverse of $A$ as $A^{\dagger} := V\...
0
votes
1answer
47 views

Finding the number of all possible pair products less than the product of two given numbers

Suppose the are two lists X,Y each has numbers from 1 to 110 , we are given given a element from X,Y each, then we have to find number of possible pair of factors from X,Y so that the product of each ...
1
vote
0answers
86 views

Writing the dual of a linear minimisation problem

I am trying to write down the dual of a linear minimisation problem and I would like your help to double check whether I'm doing it right. I'm following the instruction here . The original ...
0
votes
1answer
17 views

Method of determining the correct side

In Linear Programming, we use the “origin side” method to determine which side is the “>” side of the straight line $f(x, y) = 0$. I know it is NOT necessary true that $f(x, y) > 0$ is always on ...
0
votes
1answer
34 views

How does row operation work in the simplex algorithm?

Reading through the wikipedia page for the simplex algorithm and I can't figure out how the row operation they have as an example works... $$ \text{Minimize} \\ Z = -2x - 3y - 4z \\ \text{Subject To} ...
2
votes
0answers
23 views

Weird subspace/equality-constrained LP problem/variant of change-making problem

Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve $$\sum_{i=1}^n c_i\leq\delta$$ $$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$ where $0\...
1
vote
1answer
46 views

Travelling salesman problem visiting different nodes different times [closed]

Hi I am trying to solve a more complicated travelling salesman problem (shortest path visiting all nodes in a directed graph), where (1) I need to revisit different nodes for different times, (2) I ...
2
votes
1answer
57 views

Linearize a constraint

I have intermediate knowledge of optimization and mathematical modeling I have this constraint. I know how to model it with integers (which leads to a mixed-integer linear program). However,I was ...
1
vote
0answers
127 views

Basic solution and linearly independent columns - exercise 2.3 Bertsimas and Tsitsiklis

I am trying to solve exercise 2.3 of the book "Introduction to linear optimization" by Bertsimas and Tsitsiklis, which states: $\textbf{ Exercise 2.3 (Basic feasible solutions in standard form ...
3
votes
1answer
84 views

Determining if a Vector is a member of a Convex Hull

Edit: Here is how the following sets are created: $S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear ...
1
vote
0answers
35 views

Why are the variables in the dual linear program the shadow price?

Good evening. In lineary optimization, we have primal and corresponding dual programs. It is often said that the variables in the dual program can be interpreted as the shadow price for the ...
2
votes
1answer
32 views

How can I adjust the coefficients in the constraints of a Linear Programming problem with no objective function until I get a solution?

I have a system of linear equations that I need a solution for that is strictly positive. I have 4 solutions and 4 unknowns, and the solution I obtain for my current system involves negative numbers. ...
3
votes
1answer
78 views

Feasibility region of LP

Consider the problem $$ \text{ Find } y \text{ s.t. } \\ \exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx $$ where $y$ is a $2\times 1$ vector of unknowns, $x$ is a $10\...
2
votes
0answers
32 views

Inverting Linear System of Inequalities

I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities: $$m\leq m' \leq p+m$$ $$m \leq m'-z' \leq p+m$$ $$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$ (The last one is an equality)....
1
vote
1answer
188 views

Simplex method can't solve assignment problem?

The problem: I am trying to solve http://acm.timus.ru/problem.aspx?space=1&num=1076 , it's an online judge for programming problems. The problem could be solved by a simple application of an ...
0
votes
0answers
17 views

Runtime of source with varying resource consumption

This question is regarding a simple problem, which can be posed for different physical situations. I am posing for a particular physical situation, but the idea is to exposit the general mathematical ...
2
votes
1answer
112 views

Linear Programming and graphing (Mathematics in thw Modern World)

I need help with the #1 question. linear Programming is applied. 1. Consider the recipes below: ...
0
votes
0answers
30 views

Why do the conditions have to be smaller than in linear programming?

The basic problem in linear programming is: max $ c^Tx $ $ Ax \leq b $ $ x \geq 0 $ But why does the condition have to $ \leq $ instead of $ \geq $ ? In fact, when considering the dual problem, it ...
0
votes
0answers
19 views

relaxation of vertex enumeration problem?

The vertex enumeration problem is to find the vertices of a set defined by a set of inequalities $\{x \in \mathbb{R}^n: Ax \le b\}$. It is an open question whether, if this set is known to be bounded, ...
1
vote
0answers
14 views

finding coefficient of “Max Z = $ax_1 + bx_2 + cx_3 + dx_4 + ex_5$” given a similar constraint?

I was given a primal problem as follows: Max Z = $ax_1 + bx_2 + cx_3 + dx_4 + ex_5$ Subject To: $a_1x_1 + b_1x_2 + c_1x_3 + d_1x_4 + e_1x_5 \geq F$ $a_2x_1 + b_2x_2 + c_2x_3 + d_2x_4 + e_2x_5\geq G$...
1
vote
0answers
133 views

Simplification of a min-max problem

I have an optimisation problem to solve. The book I'm following says that the original problem can be rewritten in a simpler way by observing that one of the unknowns is a subset of the $Y-1$ ...
0
votes
0answers
28 views

Optimizing a linear sum under a system of linear constraints, does this identify legit subproblems?

A legit subproblem of a problem is loosely defined as a smaller sized problem than the original input, but if you solve this smaller problem first, then the original input becomes easier to solve ("...
0
votes
0answers
28 views

How does an LP's objective function value change when we shift the constraint vector?

Let's say that $\vec{x}^*$ is the optimal solution to the following LP: $$\begin{array}{ll} \text{maximize} &\vec{c}^{\top} \vec{x}\\ \text{such that} &A \vec{x} \leq \vec{b}\\ &\vec{x} \...
0
votes
0answers
30 views

Optimization problem with Excel's resolutor

I'm struggling to translate into Excel Language this optimization problem: \begin{matrix} \textrm{min}F\\ F-(1.150x_1+1000x_2+1350x_3)-S_1=430\\ (0,08875x_1+0,0555x_2+0,1175x_3)+1,04S_1-S_2=210\\ (...
0
votes
0answers
17 views

network flow dual simplex

In the problem P, the constraint (inequalities) on the capacity of the side is removed, and the relaxed problem is P1. let the potential of each vertex corresponding to ①,②,③,④,⑤ is y1,y2,y3,y4,y5 ...
1
vote
1answer
51 views

Proving a theorem related to polyhedra, hyperplane and face in linear programming

I'm trying to prove the following theorem about linear programming from my textbook Given a polyhedra $P=\{x\in \mathbb{R}^n|Ax\le b\}$ and a non-empty subset $F$ of $P$, then $F$ is a face of $P$ ...
0
votes
0answers
45 views

Maximizing $\max_{i\in I}(c_i^{\mathsf{T}}x+d_i)$

I'm looking for an approach to solve (computationally, in the long run) $$\begin{array}{rr}\text{maximize} & \max\{c_i^{\mathsf{T}}x+d_i\mid i\in I\}\\ \text{subject to} & a_j^{\mathsf{T}}x\...
1
vote
1answer
28 views

LP Problem Formulating

Gotham Motor Oil Company has three warehouses which it can ship products to its three retail outlets. The demand in cans for the product Super Blend is 100 at retail outlet 1; 250 at outlet 2; and 150 ...
0
votes
0answers
35 views

Trying to Determine if an Optimal Solution from an LP Solver is Indeed Optimal

Suppose we have the following LP problem: $$min\ C^Tx $$ $$s.t. \ Ax = b $$ $$x>=0$$ I am trying to confirm that an optimal solution $x^*$ obtained from an LP solver for such a problem is optimal. ...
0
votes
1answer
65 views

How to get linear or polynomial approximation of $\frac{1}{1-e^{-x}}$?

In mathematical program, one of the constraint has $\frac{1}{1-e^{-x}}$ term which can't be solved by the linear/quadratic solver. Can someone please provide a way to represent this term as a linear ...
1
vote
1answer
56 views

What linear programming problem do I have? [closed]

I have a number $W\in\mathbb{R}$ and a vector $w=\left[w_1,\dots,w_n\right]^T\in\mathbb{R}^n$ such that each $w_i=i\cdot g$ where $g=const$. Usually $n\leq4$. The goal is to find a vector $c=\left[c_1,...
2
votes
1answer
72 views

Given a convex polytope, is the Chebyshev center unique?

Consider a convex polytope over n-dimensions defined by m linear inequalities. Is the Chebyshev Center (Chebyshev Center) unique? Currently, I am getting different coordinates for the center in ...
0
votes
0answers
74 views

Removing particular solution in mixed-integer linear programming

In standard format of mixed-integer linear programming: min Z >= c'x+d'y s.t. Ax+Ey<=b The solution is z_hat for x_hat and y_hat. If by some reason I must introduce a new constraint that ...