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

learn more… | top users | synonyms

1
vote
2answers
38 views

Trying to sell the most batches of animals using linear programming

I'm trying to sell the most batches of animals... Let's say I have 200 dogs, 100 cats, and 100 ferrets. ...
0
votes
0answers
43 views

Linear system equations

I need to get, preferably by a numerical method, a solutions of: $$\left\{\begin{array}{lll} 2\sum_{i=1}^n b_{ik}x_i+x_{n+1}=0&\text{for}& k=1,2\ldots,n\\ \sum_{i=1}^n x_i=0 \end{array}\right.$...
3
votes
0answers
30 views

How to reduce the number of (overlapping) constraints in a linear program?

I am trying to solve a linear program with more than 7 million constraints which could not be solved on my computer (In total around 5000 variables). In the constraints there is a overlap between them....
0
votes
1answer
27 views

ILP Problem to minimize two functions one after the other

I am working with a ILP problem. In the problem I would like to minimize f(x0+..+xn) and then if multiple optimal solutions exist, minimize ...
1
vote
1answer
15 views

Linear programming.

In the given diagram the co-ordinates of B and C are $(-2,-1)$ and $(-2,8)$ respectively. The shaded region inside the $\triangle ABC$ represented by three inequalities. One of these is $x + y <=6$....
0
votes
0answers
11 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
1
vote
1answer
34 views

How to convert a non-linear constraint to a linear constraint for integer programming?

I have non-linear scheduling model and I want to convert it to a linear model. But I have no idea about how can I do it. The nonlinear constraint is: For each $i, i'\in I$ and $j, j' \in J$ and $q, ...
-1
votes
1answer
35 views

Knapsack problem

Knapsack problem we can solve several methods: dynamic programming branch and bound greedy method genetic algorithm Brute force Heuristic by the value / size Which of these methods gives ...
0
votes
1answer
48 views

How to linearize the following constraint on abs terms with coefficients of mixed signs

I am implementing an optimization program on 2 variables with a constraint of the form: 2*|x1| + 3*|x2| <= 2.25 * (|x1| + |x2|) Given that the effective coefficients on the two abs terms are + ...
0
votes
0answers
33 views

Linear Programming - Complementary Slackness

I just can't understand the question below: This question is presented in Exercise 5.2 from Jon Lee, "A First Course in Linear Optimization", Second Edition (Version 2.1), Reex Press, 2013/4/5. ...
2
votes
1answer
28 views

Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
0
votes
0answers
14 views

Linear Programming - Constraints

I am trying to encode this (a small part of a project that I am trying to do by self-learning) to linear programming: For each package p we know its length (xDimp) and width (yDimp). Also, we have ...
1
vote
0answers
22 views

Calculating block diagonalization / canonical bases with linear optimization?

In Linear Algebra there are many types of similarity transformations $${\bf A} = {\bf T}^{-1}{\bf DT}$$ Where $\bf D$ is (block-)diagonal. Famous examples include Eigenvalue decompositions, Jordan ...
1
vote
0answers
23 views

Enlarging a rectangle around its origin, to fit a containing rectangle, but the rectangle must be moved

EDIT: The math was easy/as expected. The bug was in a programming error related to HTML/CSS. Sorry everyone, thank you. I am coding a mobile UI where there is a view of a small card. When clicked, ...
2
votes
3answers
25 views

How to draw the graph of the optimised function in linear programming

Ok, I don't know if I am just over thinking this, but I have been tearing my hair out trying to think about this. I have looked at plenty of linear programming examples and solutions online and I can'...
0
votes
0answers
12 views

Existence of solutions for a scaled integer linear inequality

Assume that I know there exist non-negative integer solutions to a linear system of integer equations (with coefficients from $\{-1,0,1\}$ and non-negative constant terms in my case). Is there any ...
0
votes
0answers
17 views

Optimize matrix multiplication when one matrix is the same.

I have a situation where I will be multiplying $AB\vec{x}$ together frequently. $A$ is a 4x4 matrix that won't change from problem to problem. $B$ is a 4x4 matrix that will change occasionally, and $\...
4
votes
2answers
37 views

Balancing recipe's ingredients through a system of linear equations: is it the right approach?

I have 4 ingredients that I want to combine to prepare a drink: ...
0
votes
1answer
19 views

Linear equation system to standard form

So I have this linear equation system: $inf \{3x_1 - x_2 - 2x_3 + x_4\}$ $x_1 + 4x_2 - x_3 - 3x_4 ≤ 3$ $-2x_1 + x_2 + 2x_3 - x_4 ≥ -1$ $5x_1 - 3x_2 + x_3 + 2x_4 ≤ 4$ $x_1 ≥ 0, x_2 ∈ R, x_3 ≤ 0, x_4 ...
3
votes
1answer
30 views

Transforming a $0$-$1$ knapsack problem into the standard form

I have the following $0$-$1$knapsack problem: $$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 \...
1
vote
0answers
36 views

Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem: There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix: $$\begin{pmatrix} ...
1
vote
0answers
18 views

Linear programming is continuous

Consider an arbitrary linear program: $$\max \vec c \cdot \vec x$$ subject to: $$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$ Assume that this program is feasible and bounded. ...
2
votes
0answers
27 views

Show that matrix is totally unimodular

I want to show that this matrix is totally unimodular: \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & ...
1
vote
1answer
21 views

A more general case of assignment problem

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more general problem: for given $n \times m$ table select several numbers, maximizing ...
2
votes
0answers
7 views

How to get inequality representation of cone give by generators

To be as specific as possible, I have a subspace $I \subset R^{14}$ of dimension $3$ and an $11\times14$ matrix $A$ with linearly independent rows spanning the orthogonal complement of $I$. I have an ...
2
votes
2answers
45 views

linear programming infeasibility, dual & primal relation

By the strong duality theorem we know that LP can have 4 possible outcomes: dual and primal are both feasible, dual is unbounded and primal is infeasible, dual is infeasible and primal is unbounded, ...
-1
votes
2answers
35 views

Solving a linear problem using complementary slackness condition

Question $\max \space\space z= 8x_1 + 6x_2 -10x_3+20x_4+2x_5$ $\text{s.t.}\space\space\space\space\space 2x_1+x_2-x_3+2x_4+x_5= 25$ $\space\space\space\space\space\space\space\space\space\...
2
votes
0answers
16 views

Is there a good term for pairs of related variables in a system?

(Non-mathematician here. Sorry). Suppose you have a problem with lots of unknowns. The problem allows many solutions (possibly infinite). Certain pairs of unknowns (you don't know which ones) ...
0
votes
0answers
18 views

Total support in matlab

I need help writing an algorithm in Matlab telling me if a radom matrix has total support or not. I'm trying to use the Linprog formula, but I don't understand it.
1
vote
1answer
40 views

Method to convert a worded problem to a linear problem

Acme manufacturing company has contracted to deliver home windows over the next $6$ months. The demands for each month are $100, 250, 190, 140, 220,$ and $110$ units, respectively. Production cost per ...
1
vote
1answer
36 views

Is this a correct formulation of a linear programming problem?

I apologise as English is not my first language so sometimes I get stuck on problems like these as it can confuse easily. Show & Sell can advertise its products on local radio and television ...
0
votes
0answers
7 views

the optimal solution of $min$ $-x-y+(1/2)(x+2y-3)$

the optimal solution of $min$ $-x-y+(1/2)(x+2y-3)$ s.t. $x,y=0,1,2, or $ $ 3$ Attempt: if we tale the gradient of the objective function we have $[-1/2,0]^T$. This means that y could take any ...
0
votes
1answer
18 views

Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ &2x_1&+x_2&...
0
votes
0answers
10 views

Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

How would you quantify the computational complexity of feasibility LPs? Say for example an LP with $m$ inequalities : $$ \begin{cases} \mathbf{a_i}.\mathbf{x} \leq b_i, i \in [m] \\ \mathbf{x} \in \...
0
votes
1answer
20 views

Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
0
votes
0answers
29 views

Extreme Points, BFS, Extreme Directions

I'm trying to prove the two theorems below. 1) Every basic feasible ray of standard-form (P) is an extreme ray of its feasible region. 2) Every extreme ray of the feasible region of standard-form (P)...
0
votes
1answer
27 views

All faces of the n-dimensional hypercube

I am asked to determine all faces of the $n$-dimensional hypercube $$C_n = \left\lbrace x\in\mathbb R^n \;|\;\forall i\in\lbrace1\ldots n\rbrace : |x_i|\leq1\right\rbrace $$ I already know that the ...
1
vote
1answer
37 views

Linear Programming, with slack variables [closed]

I'm trying to prove the following statement Show that the set ${\{(x,w) \in \mathbb R^n\times \mathbb R^m \mid Ax \leq0, c^T x >0,w^TA=c, w\geq0 \}}$ is empty, where $A\in \mathbb R^{m\times n}$...
1
vote
1answer
29 views

Solving Linear Optimization Problem with Shortest path Algorithm

A little while ago I read a wiki about alternating between linear programming and shortest path problem (https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation). I'm just ...
0
votes
0answers
9 views

Three variable linear diophantine.

Assume I know $a,b,c,d\in\Bbb N$ in $ax+by+cz=d$ and I know there is an unique $x,y,z>0$ such that this holds can I find such $x,y,z$ in $O((\log (abcd))^\alpha)$ time for some fixed $\alpha>0$?
1
vote
2answers
36 views

Transforming a worded problem into a Linear Problem system of equation

(Advertising problem) Show & Sell can advertise its products on local radio and television (TV). The advertising budget is limited to $£10,000$ a month. Each minute of radio advertising costs $£15$...
0
votes
0answers
8 views

Why $x_B=\tilde b +\tilde A x_{\bar B};c^Tx=\psi+\tilde c^Tx_{\bar B}$ doesn't describe an optimal solution iif $\tilde c_i\le 0,\forall i$

How to counterprove the assertion that if a feasible dictionnary in the type \begin{cases} x_B=\tilde b +\tilde A x_{\bar B}\\c^Tx=\psi+\tilde c^Tx_{\bar B} \end{cases} describe an optimal ...
-1
votes
1answer
72 views

Linear Programming - The Big M Method - Proof questions [closed]

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 ...
1
vote
1answer
38 views

piecewise linear minimization equivalent to linear programming

Why is \begin{equation} \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} equivalent to an LP \begin{equation} \begin{aligned} & \min & &...
0
votes
1answer
29 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
15 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 ...
2
votes
0answers
23 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 ...
1
vote
1answer
32 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 \end{...
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 hint ...
0
votes
0answers
20 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 <...