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

learn more… | top users | synonyms

1
vote
0answers
23 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
0
votes
2answers
48 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, ...
0
votes
0answers
12 views

How to find the Lagrangian dual function (for three variables)?

How to find the Lagrangian dual function: min$-3x_1-2x_2-x_3$ s.t. $2x_1+x_2-x_3-2\le0$ $x_1+2x_2-4\le0$ $x_3-3\le0$ $x_1,x_2,x_2\ge0$ over $X=\lbrace (x_1,x_2,x_2):2x_1+x_2-x_3-2\le0;x_1,x_2,...
1
vote
1answer
27 views

how to find extreme points for 3 variable linear programming

It is rather easy to find extreme points in 2 variable case. But to find them for higher dimensions, for example in 3 variable case. For instance, min $-3x_1-2x_2-x_3$ st. $2x_1+x_2-x_3\le2$ $x_1,...
1
vote
0answers
43 views

Two problems related to the Hitchcock transport problem.

I try to solve the following two problems related to the "Hitchcock Transportation Problem" which reads as follows :$$min \sum_{i=1}^N\sum_{j=1}^Mc_{ij}x_{ij}$$subject to$$\sum_{j=1}^Mx_{ij}=a_i\space\...
0
votes
0answers
21 views

Finding a suitable solver

I have a problem finding a solver that can solve a mathematical programming model with a quasi quadratic object function. I have tried some commercially available quadratic and non-linear solvers, but ...
0
votes
0answers
28 views

How to find extreme directions?

objective:min $−3x_1−2x_2−x_3$ The set is : $X=\lbrace (x_1,x_2,x_3):2x_1+x_2-x_3\le2; x_1,x_2,x_3\ge0 \rbrace$ Attempt: $2d_1+d_2-d_3\le0$ (a) $d_1+d_2+d_3=1$ and $d_1,d_2,d_3\ge0$ Since from (...
0
votes
0answers
40 views

Solving a modified numerical heat equation

I'm having a bit of trouble finding a good numerical form for this modified version of the heat/diffusion equation and I was just wondering if I am tackling this question the correct way. Firstly, I ...
1
vote
1answer
87 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 ...
0
votes
0answers
4 views

What is $y$ in $yA_p<c^T_p$ linear programing equation?

Let be the following linear program using the revised simplex method from $B=\{x_1,x_2,x_5\}$ \begin{cases} \max & 3x_1 &+x_2\\ &x_1 &-x_2 &\le -1\\ &-x_1 & -x_2 &\le -...
0
votes
1answer
18 views

What varialbes enter the $\min/\max$ in dual problem?

Having the following linear program: \begin{cases} \max & -x_1 & -2 x_2&+x_3\\ & -3 x_1 &+x_2 & &\le -1\\ & x_1 &-x_2 & &\ge 1\\ &-2x_1 & +7 x_2 &...
2
votes
1answer
44 views

Maximum of minimums

Suppose $v_1,\ldots, v_k \in \mathbb{R}^n$ are vector with all coordinates non-negative. How to explicitly calculate: $$ \max_{x\geqslant 0, ||x||_1=1} \min_{1\leqslant i \leqslant k} <x,v_i>$$ ...
0
votes
0answers
26 views

equality constraints and conic constraints in Sedumi (SOCP)

I´m starting playing with Sedumi. I want to solve a problem in the form $$ \min c_0' x $$ s.t. $$ A_1 x = b_1$$ $$ ||A_2 x + b_2|| <= c_2'x+d_2 $$ where $x \in R^n$, $ A_1 \in R^{m_1,n}$, $ ...
1
vote
0answers
64 views

Finding all lattice point in bounded region

I have a closed region in n-dimensional space bounded by two inclined hyperplane and plane along the axes. What algorithm can I use to locate all the lattice points in the region? $$ \sum_{i=0}^n ...
1
vote
1answer
17 views

Relationship between Primal and Dual problems

Considering the following program: \begin{cases} \max & 8x_1 & + 3x_2\\ & x_1 &-6x_2&\ge2\\ & 5x_1 +&7x_2&=-4\\ &x_1&&\le 0\\ && x_2&\ge 0 \end{...
1
vote
0answers
18 views

What is the initial tableau for simplex method with big M method for this problem?

I have an optimization problem with formulation: min f = x1+x2+x3 subject to: x1+2*x2+x3=8 2*x1+x2+x3=12 x1,x2,x3>=0 I should solve it by Big M method. For this I added two extra variables (a1,...
1
vote
0answers
41 views

Dual and Primal in Linear programming.

I am stuck on these two questions. I have tried to get information on these but what am getting is not even close to the questions. What can you say about the dual if you already know that : an ...
3
votes
2answers
91 views

What programing language Thomas Hales used in 1998 to prove Kepler’s conjecture?

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal ...
0
votes
0answers
15 views

Primal + Dual relation with Complementary Slackness.

If let's say there exist an optimal solution to the primal with $x_1 = 0$, what can we deduce about the dual? Here is my attempt to answer this particular question: Since there exist an optimal ...
1
vote
0answers
21 views

Remove redundant vertices in graph

My group is currently working on a project concerning Combinatorics: Graph-theory and optimization. In the project we need to find the optimal sales strategy to the following problem. Background ...
0
votes
0answers
29 views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
0
votes
0answers
34 views

An polynomial time algorithm to solve LP

Is there a polynomial time algorithm that gives the extreme point as output for which objective function is minimized/maximized ? I am not looking for any solution that minimizes/maximizes the ...
0
votes
0answers
28 views

Optimization using Linear programming

I have a set of machines in the cloud (charged hourly). Some of them have been running already. I want to add and remove these machines dynamically in the cloud. Each type of machine has a ...
0
votes
1answer
23 views

How many tight constraints does a linear program have?

I have the following constraints of a linear program: $$\sum_{j=1}^{m}x_{ij}=1,\quad\quad1\le i\le n,$$ $$\sum_{i=1}^{n}p_i^k x_{ij}=1,\quad\quad1\le j\le m,\;1\le k\le d,$$ $$x_{ij}\ge 0,\quad\quad1\...
0
votes
0answers
13 views

optimize search through parameter space to find parameters sets

I have a simulation which calculates the amount of time it takes for a tank/tube to drop below a certain temperature, given a set of parameters. The simulation takes quite a while to run and I would ...
3
votes
1answer
67 views

Bland's Ratio Details

Bland's Finite Pivoting Method is often used as the standard pivoting rule in simplical optimization for linear programs. However, some literature conflicts - for maximization, some state that only ...
0
votes
0answers
17 views

linear inequalities and reduction

Let $X\subset \mathbb R^m$ be a convex compact subset. Let $E=\{-1,0,1\}^m$. What would be the necessary or sufficient conditions on $X$ such that for any $f\in [-1,1]^m$, there exists at least ...
0
votes
1answer
48 views

Minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k

For $k\in N, n-2\ge k\ge2$, and $n \in N, n\ge4$ minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k EDIT: Attempt to solve First I differentiated it partially w.r.t $k$ and ...
1
vote
0answers
51 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where $i=...
1
vote
1answer
36 views

Challenging Linear Programming Question - Determining Objective Function

Working Out: X = Num. of bottles sold from Vineyard 1 Y = Num. of bottle sold from Vineyard 2 A = Num. of bottles demanded by Rest 1 B = Num. of bottles demanded by Rest 2 C = Num of bottles ...
0
votes
2answers
66 views

How to generate a feasible point for a program with both equality and inequality contraints?

I am using an optimization method that requires a starting point within the feasible domain: $$\min f(x)$$ $$Ax=b$$ $$Cx>r$$ where $$x \in R^l$$ $$b \in R^n$$ $$r \in R^m$$ and $$ (m+n) &...
0
votes
0answers
18 views

How to calculate the Bouligand derivative (B-derivative)

Let $H(x)=\min (f(x),h(x))$ where $f$ and $h$ are continuously differentiable functions from $\mathbf{R}^n$ to $\mathbf{R}^1$. The Bouligand derivative (B-derivative) $BH(z)$ at $z$ of $H$ is given ...
0
votes
0answers
26 views

How does changing the cost vector of a primal linear programming problem affect the solution of the dual?

Say the linear program: max $p'x$ such that $Ax=b$ and $x \geq 0$ is primal and dual feasible, and $\bar{u}$ is known to be the optimal solution to the dual. If the $\lambda \ne 0$ times the $i$th row ...
0
votes
1answer
35 views

Formulating the Dual of a linear program

I have a linear program: Maximize 18x + 12y subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0 I have found ...
0
votes
0answers
11 views

Use duality to solve LPP

I have some confusion regarding the solution of LPP by solving its dual. I have drawn the following table to indicate possibility/possibilities. I have made an attempt to correlate the two columns but ...
0
votes
1answer
15 views

Unbounded solution of LPP

In connection with LPP, what is meant by 'unbounded solution' and 'unbounded objective function'? Are they same or they are distinct concepts?
2
votes
2answers
152 views

Why can/should we use 5 instead of 10?

Problem: A pharmacy has a uniform annual demand for 200 bottles of a certain antibiotic. It costs \$10 per year for a storage place for one bottle, and $40 to place an order. How many times during ...
0
votes
0answers
23 views

Conditionals without use of binary variables

I would like a linear programming expression that has to satisfy certain criteria without the use of binary variables. i.e.: Let 0 <= B <= C However, if ...
0
votes
1answer
17 views

Graphical solution of lpp

I need to solve the following LPP using graphical method Min $z=-2x_1+x_2$ subject to $x_1+x_2 \geq 6$, $3x_1+2x_2 \geq 16$, $x_2 \leq 9$, $x_1, x_2 \geq 0$ The common feasible region is ...
0
votes
0answers
27 views

Mathematical formulation of LPP

I want to formulate the following problem as a LPP A manufacturing company produces two types of computer monitor- color and monochrome. The data in the manufacturing context are as follows 6 days ...
0
votes
0answers
26 views

Definition of Concave set

We know that a set is convex if the straight line joining any two points of the set lies completely in the set. or mathematically a set $X$ is convex if $x_1, x_2 \in X \Rightarrow\lambda x_1+(1-\...
1
vote
2answers
45 views

Optimization over linear combinition of min functions

Assume we are given these six variables: $x_{12},x_{21},x_{13},x_{31},x_{23},x_{32}$. Then if, $A_{ij} = min\{x_{ij},x_{ji} \}, B_{ik} = min\{x_{ik} - A_{ij}, x_{ki} \}, C_{jk} = min\{x_{jk} - A_{ij},...
0
votes
0answers
10 views

Estimate size of smallest solution to linear program

I have a linear program: a system of linear inequalities of the form $$Ax \le b, \qquad x \ge 0.$$ where $x \in \mathbb{R}^n$, $b \in \mathbb{R}^m$, and $A$ is a $m\times n$ matrix. I am looking ...
0
votes
1answer
49 views

Prove a set is convex

I have problems to make proof for below two statements. Let Γ be the LP max cᵀx s.t. Ax ≤ b. prove that set of all optimal solutions to Γ is a convex set Let x' be a basic feasible solution of Γ. ...
0
votes
1answer
51 views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
1
vote
1answer
37 views

Vertex and barycentric coordinate enumeration for a polytope

Problem 1 Enumerate all the vertices of the polytope defined by: ${\bf Ax}\leq {\bf b}$ where ${\bf A} \in R^{m \times n}$, ${\bf x} \in R^n$, ${\bf b} \in R^m$ and each element of ${\bf x} = \{x_1,...
0
votes
1answer
35 views

Finding the dual of a LP

I am trying to find the dual of the following linear program. The primal LP's purpose is to find the lowest possible L1 (sum of absolute values of coefficients) of a degree $d$ polynomial such that (1)...
2
votes
1answer
22 views

Express the feasible solution (3,1) as a convex combination of extreme points

So i am given four extreme points: $A: (0,0)$ $B: (8,0)$ $C: (2,3)$ $D: (0,1)$ and I need to express the feasible solution $(3,1)$ as a convex combination of extreme points. My professor did the ...
0
votes
1answer
25 views

proof of existence of solution to componentwise inequality using only linear algebra

For $A \in \mathrm{Lin}(\mathbb{R}^n, \mathbb{R}^m)$ , $m=n$ and $A$ is invertible, I am able to prove the existence of a solution $x$ such that $A x \succeq 0$ where $\succeq$ denotes componentwise ...
-1
votes
1answer
78 views

Linear Programming Mixed Assortment of Nuts

Below is a problem on Linear Programming. I think I have a start to it, but I'm in a rut right now so I was wondering if I could receive a little help. Here's the problem A candy store sells three ...