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

learn more… | top users | synonyms

0
votes
0answers
19 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 ...
0
votes
0answers
19 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 ...
1
vote
0answers
22 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
12 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 ...
5
votes
0answers
41 views

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 ...
1
vote
1answer
35 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 ...
0
votes
0answers
21 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
36 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
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, ...
0
votes
0answers
10 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 ...
1
vote
0answers
10 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
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$, ...
1
vote
1answer
59 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 ...
2
votes
1answer
29 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
1answer
37 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
26 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. My book says that this is a corollary to complementary slackness. What's ...
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 ...
5
votes
2answers
204 views

Convert a piecewise linear non-convex function into a linear optimisation problem.

Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different. Convert $$\min z = f(x)$$ where $$f(x) = \left\{\begin{matrix} 1-x, ...
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
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
15 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
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
14 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
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
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
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
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 ...
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
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 ...
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) \\ && ...
1
vote
0answers
45 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
2answers
54 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 ...
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\\ ...
1
vote
0answers
32 views

Model linearly: Determine amount of units for production

A company produces 2 products in a week. Let $x_i$ denote the number of units of product $i$ to produce. Each product requires liters of Chemical X to make. Info is given below: ...
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 ...
0
votes
0answers
37 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
votes
1answer
23 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
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$ ...
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
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 ...
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.