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

learn more… | top users | synonyms

1
vote
1answer
24 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, ...
0
votes
1answer
20 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
13 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
1answer
47 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
8 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
0answers
20 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
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 ...
1
vote
1answer
36 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 ...
4
votes
2answers
37 views
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. ...
1
vote
1answer
288 views

Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region $(X)$ of a Linear Program can be represented as a convex combination of the extreme points of $X$ plus a non-negative combination of the extreme ...
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
627 views

Binary constraint integer programming problem

I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let $x$ and $y$ be integer variables bounded at 1000. How can you ...
0
votes
0answers
11 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 ...
5
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\\ ...
3
votes
2answers
277 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
1
vote
0answers
21 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 ...
12
votes
3answers
268 views

When does a variable leave a basis (in linear programming)?

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 ...
0
votes
0answers
10 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 ...
0
votes
0answers
82 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. ...
2
votes
2answers
277 views

Simplex method - multiple optimal solutions?

I have to solve this optimization problem: $$\begin{array}{ll}\text{minimize} & z= x_1 - x_2 + 3x_3\\\\ \text{subject to} &x_1-x_2+x_3-x_4=2\\ & 2x_1-2x_2-x_3+x_5=0\\ & x_1, x_2, x_3, ...
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 ...
1
vote
2answers
913 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
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 ...
0
votes
1answer
388 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
1
vote
1answer
3k views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
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} ...
5
votes
2answers
202 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
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 & ...
3
votes
1answer
805 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax ...
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
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, ...
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 ...
0
votes
1answer
30 views

Can an unfeasible solution be optimal in an LPP

In a linear programming problem, Is it possible to have an unfeasible solution that is optimal?
-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$ ...
0
votes
1answer
56 views

Setting up an LP problem on producing linear board in jumbo reels

I have to set up a linear programming problem corresponding to the following scenario: What I tried: I think we have 8 templates for 1 $68 \times l$ reel (or whatever): $22,22,22$ (66) ...
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) ...
2
votes
2answers
547 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
3answers
50 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1=1$ ...
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.
3
votes
1answer
3k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
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 ...
2
votes
1answer
555 views
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
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 ...
1
vote
0answers
50 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where ...