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

learn more… | top users | synonyms

1
vote
0answers
29 views

How to define backup paths? Flow networks / virtual network embedding / Linear Programming

I'm working in virtual network embedding, where, in short, there is a physical network in which the links and nodes of a virtual network have to be mapped, taking into account some constraints, such ...
0
votes
1answer
46 views

Linear Programming: Maximize

Jimbo Enterprises produces $n$ products. Each product can be produced in one of $m$ machines. Let $t_{ij}$ be the time in hours needed to produce one unit of product $i$ on machine $j$. For month $k$, ...
0
votes
2answers
30 views

$\max 2x_1 +x_2$ unbounded or unfeasible with the constraint $sx_1 +tx_2\le-1$

\begin{cases} \max & 2x_1 &{}+x_2\\ & sx_1 &{}+tx_2&\le-1\\ & x_1,x_2&&\ge 0 \end{cases} Find out when this program is not feasible, bounded Feasibility It ...
2
votes
1answer
30 views

Use of binary variables in LP problems

I can't figure out how to write the following condition to an LP. I have four nonnegative variables: $X_A$, $X_B$, $X_C$, and $X_D$. The condition which should be satisfied is this: If $X_A$ and ...
1
vote
0answers
58 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 ...
1
vote
2answers
173 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
0
votes
1answer
20 views

Can a network migration problem be solved with linear programming

I'm trying to solve, using linear programming, the problem of determining in which order should network elements by migrated from one place to another. The idea is that resources such as bandwidth ...
1
vote
1answer
18 views

Linear Programming Diet Problem

I'm just starting to explore linear programming in Excel and have hit a VERY newbie problem I'm sure. I'm using it to optimise a "diet" plan with a few ingredients. The problem I've hit is as ...
1
vote
1answer
28 views

Solve dual of linear program without simplex

I have a linear program and need to determine and solve the dual program. The primal program is $\begin{array}{lcl} \text{Maximize: }\\ f(x) := 6x_1+4x_2\\ \text{Subject to:}\\ -2x_1-4x_2 \leq ...
0
votes
0answers
16 views

(Revised Simplex Method) How is B-inverse computed in this Linear Optimization example?

I've been trying to figure this out for a while, so I'm hoping somebody might be able to shed a few insights. I've been looking through this example problem that uses the Revised Simplex Method: ...
0
votes
0answers
5 views

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x$?

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x=[-115/588, -95/588, 5/14]^T$? Pseudoconvexity: If $\nabla f(\bar x)^T(x-\bar x)\ge0$, then $f(x)\ge f(\bar x)$ for any $x\in \mathbb{R^3}$ (in this ...
1
vote
1answer
68 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
1
vote
0answers
75 views

What programs or websites solve linear integer or goal programming problems?

I don't think I can use Excel. My solver doesn't work so I can't even use Excel for regular linear programming. Something like this but for integer or goal programming. This seems to allow integer ...
1
vote
0answers
13 views

Compute the singular value of matrix

I would like to prove that for a matrix $A$ with dimension $p \times q$, and dim$(A)=q$, define a p+q by p+q symmetric indefinite matrix B with zero diagonal blocks and with A and $A^T$ in the ...
0
votes
0answers
15 views

Unbounded variables and dual of a linear program

I have to find the dual of \begin{cases} \max & -x_1 &-2x_2+x_3\\ & -3x_1 &+x_2&\le-1\\ & x_1 &-x_2&\ge 1\\ & -2x_1 &+7x_2&\le6\\ & -5x_1 & ...
0
votes
0answers
20 views

Finding a particular vector given a basis

I am trying to implement a code for Karmarkar's algorithm for solving linear programming problems. I want to automate the selection of the initial vector on the basis of the constraint vector $A$ ...
0
votes
1answer
31 views

characteristic cone of polyhedral

Let $$Q=\{x ∶ Ax ≤ b \}≠∅$$ If $Q = P + C$, where $P$ is a polytope and $C$ is a polyhedral cone, prove that $$\{y|Ay ≤ 0\} = \{y|x + y ∈ Q, ∀ x ∈ Q\}$$ The cone $C = \{y|Ay ≤ 0\}$ is ...
0
votes
1answer
47 views

How to find all basic feasible solutions of a linear system?

I'm trying to solve this problem but need some help getting started. The problem asks to find all the basic feasible solutions of the following system: \begin{equation} -4x_2+x_3=6 \end{equation} ...
0
votes
0answers
23 views

Linear integer programming

I am trying to find the optimal solution for the following linear integer programming: \begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && ...
0
votes
2answers
38 views

Find the dual of the lp problem

The problem given is and I need to find the dual: Min $Z=x_1$ st. $x_1+x_2 \leq 4$ $x_2 \geq 0$ So this is what I did, I said: Let $x_1=x_1'-x_1''$ where $x_1',x_1'' \geq 0$ So now ...
0
votes
2answers
56 views

What method will work for this linear programming problem?

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
36 views

Dependence of the derivative of a pseudo-Boolean function on its variables

I am going through Pseudo-Boolean optimization by Boros et al. In the section 2, the paper introduces the idea of derivative and residual of a peudo-Boolean function. It is claimed that both ...
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
0
votes
0answers
30 views

Integer programming with linear constraint

I am trying to find the optimal solution for the following problem \begin{eqnarray} &&\underset{x_i, ~y_i ~\forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i f_i(y_i) \\ && ...
0
votes
2answers
55 views

Questions about simplex algorithm

I'm trying to understand how simplex algorithm works, and here are my questions: 1. Why we choose the entering variable as that with the most negative entry in the last row? My understanding is that ...
1
vote
0answers
46 views

Directed Weighted Graph with no cycles - LP

I have directed weighted graph. I have to find a set of edges with minimal sum of their weights that without the set graph becomes acyclic. I can call lp solver multiple times. I'm kind off lost on ...
0
votes
1answer
21 views

How to solve a linear program with additional equality constraints?

The following optimization problem $$\max_{\substack{x \ge 0,\\Ax^T+b^T\ge 0}} c x^T$$ where $x \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, $b\in\mathbb{R}^m$, and $c \in \mathbb{R}^n$ is ...
0
votes
0answers
30 views

Is it possible to define a dual for the Rubiks Cube Problem?

The $3 \times 3$ Rubiks cube is already solved algorithmically. What I intended to do was to define Rubiks cube as a Linear Program. I found this link when I was searching for a formulation for it. Is ...
0
votes
0answers
10 views

Convert the Matching Polytope LP to Dual Program

For my course in discrete optimization I am studying about Polytopes and their dual programms. They state that the convex hull of Perfect Matchings in grahph $G=(V,E)$ is given by: $$ x\geq 0\\ ...
0
votes
1answer
35 views

Linearize non-linear constraint [closed]

I have a problem which may be defined as: $$\max 5 x_{11} + 6 x_{12} + 2 x_{21} + 3 x_{22} \\ x_{ij}\in \{0,1\} \\ x_{11} + x_{12} = 1 \\ x_{21} + x_{22} = 1 \\ t_1,t_2 \text { integer} \\ (t_1 - ...
0
votes
0answers
9 views

Finding the lower bound of a linear program with the duality method

The issue I have some difficulties understanding the lower bound of a program when applying the duality method. It seems that it comes from $$c^T\underbrace{\le}_{x\ge 0\\y^TA\ge c^T} ...
1
vote
0answers
58 views

Fourier-Motzkin - exercise

I'm going to solve this exercise but I'm stuck. Use Fourier-Motzkin elimination to compute the minimal value of $$x_1 + 2x_2 + 3x_3,$$ when $x_1$, $x_2$, $x_3$ satisfy $$x_1 − 2x_2 + x_3 = 4,$$ ...
0
votes
0answers
15 views

Linear Programming Sensitivity Analysis Problem

I am really struggling with this problem and would appreciate a detailed explanation for my studies. I have to following LPP: $Max z= x_1+2x_2+x_3+x_4$ $subject$ $to$ $2x_1+x_2+3x_3+x_4 \le 8$ ...
1
vote
1answer
21 views

Modified Transportation Problem

Could you point me to some article that tackles a problem similar to this. There are two sets: Sources $A = a_1,a_2,\ldots,a_n$ Destinations $B = b_1,b_2,\ldots,b_n$ The distance between source ...
0
votes
0answers
15 views

Linear programming exercise verification

I am working on this exercise (translation mine): A Motel provides a 24 hour service and needs a minimum number of workers depending on the time slot: ...
1
vote
1answer
24 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$ ...
11
votes
1answer
72k views

shadow price in linear programming

I am quite confused about the meaning of shadow price from explanations on the internet. It can be understood as the value of a change in revenue if the constraint is relaxed, or how much you would ...
0
votes
0answers
49 views

Prove that optimal Solution exist without solving.

![1]: http://i.stack.imgur.com/Osa3G.jpg Without solving the problem, show that it has an optimal solution.
1
vote
0answers
22 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
46 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 ...
0
votes
0answers
20 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
38 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
79 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
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 ...
1
vote
0answers
39 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 ...
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 ...
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 ...
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>$$ ...
1
vote
0answers
62 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 ...