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
47 views

Non-Empty Random Set Construction

I am aware any set $$ \mathbb{S} = \{x\in\mathbb{R}^n | A x \leq b\} $$ where $A\in\mathbb{R}^{q\times n}$, $q\in \mathbb{R}^q$ is convex, yet there is no guarantee it's also non-empty. Is there ...
1
vote
1answer
26 views

Sensitivity on A Farmer's Case

I have questions, from Bazaraa's book (Linear Programming). I have calculated point a. This is the optimal table. Where $x_1$ is wheat, $x_2$ is corn, dan $x_3$ is soybeans. My question is, what ...
0
votes
2answers
57 views

Linear programming problem and Newtonian mechanics

I am trying to learn Linear Programming. However, I don’t know how to solve the following problem. Maybe you can help, because I am curious to the right approach and solution for this problem. It ...
0
votes
0answers
10 views

linear multivariate constant (known) jacobian optimisation problem with non linear constraints

apologies if I don't give all the information needed I'm a bit out of my depth here. I have a multivariate optimisation (I think) problem: y = f(x) Where x and y are both vectors of the same ...
0
votes
1answer
49 views

Linear programming solution

How to prove a linear program that is feasible and bounded is maximised at one of the basic feasible solution?
0
votes
0answers
74 views

Can we reduce the maximization of this integral to the maximization of the integrand?

I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\Phi_g(w):=\sum_{i\...
1
vote
1answer
32 views

My matrices are non-negative,stochastic, irreducible and aperiodic, I want to know whether they always converge in power iteration.

I am working on a problem of SCC graph. The matrix representation of graph will be a square non-negative matrix that is column stochastic, irreducible. I will make it aperiodic by adding a self-loop ...
1
vote
0answers
22 views

Solution is unbounded, optimization problem in Matlab after modification.

The solutions seems to be unbounded even if the array A is changed to [-4 1 5; 4 1 5; 1 1 1]; Anything wrong with syntax. Could not figure out. Any help.
1
vote
1answer
51 views

How can we solve this simple linear program?

Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,...
0
votes
0answers
37 views

Lifting of a polyhedron

The $l_1$-ball in $\mathbb{R}^d$ is $\{x \in \mathbb{R}^d : \sum_{i=1}^{d} |x_i| \leq 1 \}$. This is a bounded polyhedron $\mathcal{P}_1$, specified by $2^d$ inequalities as $\{x \in \mathbb{R}^d :...
1
vote
1answer
35 views

Where can I find a (well-documented) simple solver for linear optimization problems with both equality and inequality constraints?

I need to solve a linear optimization problem subject to both equality and inequality constraints in C++ (using MSVC 15). Mathematically, this can be solved by the simplex algorithm. Since I don't ...
1
vote
0answers
55 views

Uniqueness of Optimal solution of simplex

I have following simplex problem $$\begin{array}{ll}\text{minimize} & z= -2x_1 - 3x_2 -6x_3\\\\ \text{subject to} &2x_1+x_2+x_3\le5\\ & 3x_2+2x_3\le6\\ & x_1, x_2, x_3 \geq 0\end{...
2
votes
0answers
25 views

Structure of an Optimal Solution to a Fractional Packing Problem

Packing LP We have the following optimization problem: $$ \max_{x_{ij}} x_{ij} c_{ij}$$ s.t. $$(i)\forall j\mbox{ }\sum_{i} x_{ij} \leq \beta_j$$ $$(ii)\forall i\mbox{ }\sum_{j} x_{ij} D_{ij} \leq 1$...
3
votes
1answer
66 views

Proving optimal solution for Linear Programming

Suppose we have a standard optimization problem. $A'$ is an optimal solution to the problem. If we add a constraint to our original optimization problem, and $A'$ satisfies the new constraint, then is ...
1
vote
2answers
45 views

Is the solution to Mean Squared Error also the one to Mean Absolute Error?

When I was dealing with optimization problem and deciding whether to minimize MSE or MAE, I had the following question: Is the solution to Mean Squared Error also the one to Mean Absolute Error? If ...
1
vote
1answer
65 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
42 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
52 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
36 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
30 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
98 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
47 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
75 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
20 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
45 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
45 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
33 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
45 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
54 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
121 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
82 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
34 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
30 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
77 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
31 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
153 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
105 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 ...