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

learn more… | top users | synonyms

0
votes
1answer
28 views

Linear Programming - The Big M Method - Proof questions

I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance. Q: It is possible to combine the two phases of ...
0
votes
0answers
17 views

piecewise linear minimization equivalent to linear programming

Just ask a dumb problem: \begin{equation} \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} is equivalent to an LP \begin{equation} ...
0
votes
1answer
11 views

Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
0
votes
0answers
11 views

Linear programming: neighbor vertices

In this document http://www.princeton.edu/~amirali/Public/Teaching/ORF363_COS323/F14/ORF363_COS323_F14_Lec11.pdf there is next definition: Two vertices are neighbors if they share n-1 tight ...
0
votes
0answers
7 views

Does Vogel's Approximation Method give a unique basic feasible solution? [on hold]

Does Vogel's approximation method necessarily result in a unique Basic Feasible Solution?
0
votes
0answers
14 views

Basic Linear Algebra/Root finding question

What is the general method for solving this problem? $\theta_n.1_T'.z_T=0_n$ where $\theta_n$ is a n x 1 vector of parameters that are free to vary, $1_T'$ is a 1 x T vector of ones, $z_T$ is a T x ...
5
votes
0answers
95 views
+50

When might some a variable leave the basis?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
1
vote
0answers
16 views

Linear programming: choosing entering variable

maximize 10π‘₯1 + 12π‘₯2 +12π‘₯3 subject to π‘₯1 + 2π‘₯2 + 2π‘₯3 + π‘₯4= 20 2π‘₯1 + π‘₯2 + 2π‘₯3+π‘₯5= 20 2π‘₯1 + 2π‘₯2 + π‘₯3 +π‘₯6= 20 π‘₯1, … , π‘₯6 β‰₯ 0 This is my first step for simplex tableau x1 x2 ...
2
votes
0answers
22 views
+100

Optimizing value of discrete harmonic function at a given point

Let $n>0$, and let $S_n$ denote the discrete square $S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and ...
0
votes
0answers
17 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a ...
1
vote
1answer
23 views

Write the dual LP of the primal LP problem

I have to find the dual of the lp problem given below Minimise $$z=-x_1+\frac43 x_2$$ subject to∢ $$\begin{array}[t]{l} 2x_1+4x_2\le16\\ -\frac{1}2 x_1-x_2\le4\\ -3x_1+4x_2\ge-24\\ x_1β‰₯0,x_2≀0 ...
1
vote
1answer
54 views

Is this a proper alternative way for math model for TSP(Travelling Salesman Problem)?

I have never seen a model that uses indexing in any article.So I have decided to publish it to be sure. I think indexing model is more suitable for generalizing the model than the subtour elimination ...
0
votes
1answer
1k views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
1
vote
1answer
31 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
1
vote
1answer
395 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
0
votes
0answers
16 views

$\{x\in R^n | Ax \leq b\} \cap \{x \in R^n | Dx \leq d\}= \emptyset$ iff there is a vector $c \in R^n$ such that $c^Tx < c^T y$

Consider two non-empty polyhedra $P := \{x\in R^n | Ax \leq b\}$ and $Q := \{x \in R^n | Dx \leq d\}$. Show that $P \cap Q = \emptyset$ if and only if there is a vector $c \in R^n$ such that $c^Tx ...
2
votes
0answers
166 views

Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
0
votes
0answers
45 views

What values make the solutions in the optimal? infeasible? degenerate? etc

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. We can use instead $r_1, r_2, r_3$ (r for row). I'm assuming there's a non-negativity constraint. we need to state ...
0
votes
0answers
20 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. What I tried: The short version is that unbounded primal means a column ...
1
vote
1answer
54 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 ...
0
votes
0answers
19 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: ...
0
votes
0answers
11 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
-1
votes
0answers
18 views

How do display matrix A,b,c when using AMPL for a Linear Optimization's problem?

When solving a linear program in the form max/min c^T subject to Ax=b in AMPL is there a way to display just the matrix A, b, and c. I am using the following model file and read in matrices for the ...
-2
votes
0answers
18 views

Solving linear programming problem [closed]

How to solve this linear programming problem? $$\sum_{e \in E}{w_e z_e} + \sum_{p \in P, a \in L}{c(p,a) x_{pa}} \rightarrow \min,$$ $$\sum_{a \in L}{x_{pa}} = 1, \qquad p \in P,$$ $$z_e = ...
0
votes
0answers
20 views

Which Denominations to use for payroll with no returned change

I want to solve the following problem. It is not a homework. Assume that a company pays payroll to employees every period, the sum of the salaries for period is $T$. The accountant goes to the bank ...
0
votes
1answer
35 views

Linear Optimization proof. Duality proof.

I need help with this problem. The exact problem is in this link http://d2vlcm61l7u1fs.cloudfront.net/media%2F959%2F959d289e-6f26-4e21-875e-bb71f3f5a49f%2Fphprimn1q.png Sorry for the poor formatting. ...
0
votes
1answer
638 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...
0
votes
1answer
21 views

What is the class of this Integer programming prob.

I have an optimization problem which seems to be non-linear because of the constraints (right?): $max (\sum U_i\times x_i)\\ \sum x_i\times y_i\times r_i\leq R\\ \sum y_i=1\\ \sum x_i=1\\ x_i, ...
1
vote
1answer
30 views

Markov dynamic programming recursion

I'm learning Markov dynamic programming problem and it is said that we must use backward recursion to solve MDP problems. My thought is that since in a Markov process, the only existing dependence is ...
0
votes
0answers
9 views

Formulate Maximum matching as linear programming problem - A matrix

I have following bipartite graph $G = \{V,E\}$: $$ V=\{v_1,v_2\} \cup \{v_3,v_4\}\\ E=\{e_1,e_2,e_3\}\\ e_1 = (v_1, v_3)\\ e_2 = (v_1, v_4)\\ e_3 = (v_2, v_4) $$ I'm supposed to formulate a linear ...
2
votes
1answer
93 views

Convert a piecewise linear function into a linear optimisation problem.

Consider $$f(x) = \left\{\begin{matrix} 1-x, & 0 \le x < 1\\ x-1, & 1 \le x < 2\\ \frac{x}{2}, & 2 \le x \le 3 \end{matrix}\right.$$ where $x \ge 0$. Convert $$\min z = ...
1
vote
0answers
9 views

Prove that Minimum Vertex Cover problem is dual to Maximum matching problems

So, I'm able to formulate both linear programming problems like this: I have a graph G ={V,E}. Minimum Vertex Cover: $$ min \sum_{v \in V} x_v\\ x_{v_i} + x_{v_j} \geq 1, (\forall e = (v_i, v_j) ...
1
vote
0answers
454 views

How do I convert max min problem into a linear programming problem?

Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector. Show that this problem $$\max \min (c^T x - y^T Ax + b^Ty) \text{ such that } x,y \ge 0$$ can be reduced ...
0
votes
0answers
32 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
1
vote
0answers
28 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
44 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
28 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
57 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 ...
4
votes
1answer
4k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
0
votes
0answers
53 views

min-max problem

Hello to everybody: I'm trying to prove that : Let $A$ be the incidence matrix of a clutter (simple hypergraph) $C$. Prove that the vertex covering number and the matching number of $C$ satisfy: ...
1
vote
2answers
163 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 ...
1
vote
1answer
54 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$ and $y_2 = 0$ because $x_6$ is in basis. How do I find $y_1$ and $y_3$ without going through the simplex method? I ...
0
votes
1answer
19 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
17 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
26 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
13 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
63 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
70 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 ...