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

learn more… | top users | synonyms

0
votes
1answer
12 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 ...
0
votes
1answer
12 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 ...
0
votes
0answers
7 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
21 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
28 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
46 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
23 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
25 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
10 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
19 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
20 views

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

I am coding a mobile UI where there is a view of a small card. When clicked, the card expands from its corner, to fit the view. Like so: Coding wise, this is a two-step process. The steps happen ...
2
votes
3answers
24 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 ...
0
votes
0answers
9 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
16 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
0answers
81 views

integral vertex of the polyhedron

I am trying to prove the following : If $A$ is a $\{0, 1\}$-matrix, then any integral vertex of the polyhedron $P = \{x \mid x \geq 0 ; Ax \geq 1\}$ is a $\{0, 1\}$-vector. But I cannot do it. ...
0
votes
1answer
18 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
22 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
31 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
17 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
21 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
43 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
34 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$ ...
2
votes
0answers
15 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
15 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
31 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
17 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\\ ...
0
votes
0answers
8 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
27 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 ...
0
votes
1answer
25 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
35 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 ...
1
vote
1answer
26 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
25 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 ...
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 ...
-1
votes
1answer
59 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
37 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
25 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
22 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
28 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 ...
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 ...