Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1
vote
3answers
92 views

$x,y,z$ are all strictly positive, $x+y+z=1$, what is $\max(xyz)$

$x,y,z$ are all strictly positive, $x+y+z=1$, what is $\max(xyz)$? My attempt: Using rand() function in Microsoft Excel to generate random numbers between $0$ and $1$. I used this function for the ...
0
votes
1answer
55 views

How to find minimum of linear matrix function?

Suppose I wish to minimise $$A = 1^T_{n_1} B C 1_{n_1}$$ where $B$ is a matrix of unknowns of dimension $n_1 \times n_2$ and $C$ is a constant matrix of dimension $n_2 \times n_1$, and $1_{n_1}$ is ...
1
vote
0answers
19 views

optimize/minimize linear function where each variable has “steps” that can be upgraded

I have used sklearn's linear regression function in Python to come up with a surrogate model to describe energy use (in GJ) of a residential house. The parameters are: Air changes per hour Wall ...
0
votes
1answer
20 views

Constrained Reviewer Pairing

I've been tasked to optimize the assignment of reviewers for a group assignment. The problem follows as such, we have $x_i$ student teams $i \in 1 ... n_1$ and $y_j$ reviewers $j \in 1 ... n_2$. ...
-1
votes
2answers
42 views

Linear Programing: Set binary variable 1, if two variables are not equal

I guess I have a simple problem, but I can't find a fitting solution. I have a certain amount periods $D$, and every period is described by the decision variable $X_d$. What I want to do is set a ...
0
votes
0answers
69 views

Basic solution vs. Feasible solution

What is the difference between a basic solution of an underdetermined matrix system $\textbf{Ax}=\textbf{b}$ and a feasible solution of of the linear programming problem in standard form $\ \...
0
votes
1answer
30 views

Shouldn't this be a basic feasible solution

the answer given is that it is a feasible solution, but as the variables are at 0/1 level, isnt it basic too?
0
votes
1answer
41 views

True or false questions for LP and the simplex method

True or false? (a) Deleting a constraint leaves the feasible region larger. (b) Adding a constraint leaves the feasible region either unchanged or smaller. (c) An LP cannot have an ...
0
votes
1answer
25 views

Constraining displacement of moving prize colector in linear programming

This is a linear programming question. Suppose there is one collector that is mobile and can travel between different locations. Each location offers time variable prizes, the collector gains the ...
1
vote
1answer
51 views

How to maximise constraints?

I am not sure how to interpret this problem and where to start to get my values to plot my graphs and get my x, y and etc values as there is too much going on. Can someone shed some light of how to do ...
0
votes
1answer
74 views

Special Cases By Looking At A Simplex

Given the following simplex tableau Find $\alpha, \beta, \gamma, \epsilon, \eta$ such that: The current solution is optimal, but there are infinite optimal sloutions The problem is unbounded The ...
0
votes
0answers
79 views

Reduced Cost And Shadow Prices

I have the following LP: $$\text{Max } z=2x_1+3x_2+5x_3+3x_4$$ $$\text{s.t } x_1+2x_2+3x_3+x_4\leq 5$$ $$x_1+x_2+2x_3+3x_4\leq 3$$ $$\forall i: x_i\geq 0$$ I am asked to find: 1. another optimal ...
1
vote
0answers
23 views

I want to know what is the relation between network flow min cost problem and max flow problem with simplex method linear programming,

I want to know what is the relation between network flow min cost problem and max flow problem with simplex method linear programming, such as primal dual and complementary slackness and how can i ...
0
votes
1answer
50 views

Basic feasible solution: problem in non standard form

Consider the following linear program: \begin{equation} \begin{matrix} \displaystyle \min_{x_i} & \sum_{i=1}^{m} {c_i^Tx_i} \\ \textrm{s.t.} & \sum_{i=1}^{m} A_i x_i = b \\ & x_i \geq ...
0
votes
0answers
21 views

Asign values for two variables in order to give away tickets for a draw

I want to give tickets for a draw depending on two variables (amount purchased, times purchased). The combination of these two would give a number of tickets for the draw. For example, two purchases ...
2
votes
0answers
25 views

Solving Linear Programming Via Big M method

$$\text{Max } x_1 +3x_2$$ $$\text{s.t } 3x_1+x_2\leq 3$$ $$x_1-x_2\geq 2$$ $$x_1,..,x_2\geq 0$$ So we first transform to the standard form: $$\text{Min } -x_1 -3x_2$$ $$\text{s.t } 3x_1+...
1
vote
1answer
39 views

why are the extreme points equivalent to basic feasible solutions in a linear programming problem?

Let extreme points be the set X={x greater or equal to 0 given Ax=b for vector x and b} and a point x is extreme if for all y,z in X, x=(1-a)y+az for a=[0,1] Basic Feasible solution x is if for A be ...
3
votes
2answers
128 views

find the minimum value for the following expression $\max \{ {x_{i_1}, x_{i_2}-x_{i_1},x_{i_3}-x_{i_2} … x_{i_n}-x_{i_{n-1}}, 1-x_{i_n} }\}$

Given the numbers $0<x_1<x_2<...<x_{n^2}<1$, For each sub group of n of those elements: $x_{i_1}<x_{i_2}<...<x_{i_n}$ we will look at the value of the following expression : $...
0
votes
0answers
13 views

A doubt regarding Vogel's Approximation Method

In VAM, we usually start with the row/column with maximum of differences (and we select the row/column accordingly). But, if I don't select the 'absolute maximum' and go on to start the process with ...
1
vote
1answer
43 views

Mixed-integer LP formulation with equality indicator functions in constraints

Is there a way to formulate the following Linear Program in a mixed-integer LP with big-M modelling? $\max_{w_{i}}\sum_{i=1}^{N}w_{i}\cdot C_{i}$ subject to: (1) $I\left(w_{i}=0\right)K_{2}+w_{i}\...
1
vote
0answers
50 views

$f(\lambda) = max\left \{ (c + D\lambda)^{t}x : x \in P \right \}$. is convex.

Let $A \in \mathbb{R}^{m\times n}, D \in \mathbb{R}^{m\times p}, b \in \mathbb{R}^{m} $ and $c \in \mathbb{R}^{n}$. Define $$P =\left \{ x=(x_1,x_2,...,x_n) \in \mathbb{R}^{n} : Ax=b , \forall_i \text{...
0
votes
0answers
16 views

Construct a direction of recession of the dual that is from growth to dual function.

Consider the primal problem $ min ct x $ s.a $ Ax = b, x \geq 0, $ where $ A \in \mathbb {R}^{ m × n}$ has put full line. Suppose that, in a certain iteration of the dual-simplex method, relative to a ...
2
votes
1answer
44 views

How to algorithmically decide if a given polytope is open?

Given a polytope $$P = \{{ \bf x} \in \mathbb{R}^n\mid{\bf A} {\bf x} \leq {\bf c}, {\bf A}\in\mathbb{R}^{m\times n},{\bf c}\in\mathbb{R}^m\}$$ find a fast algorithm that determines if $P$ is ...
1
vote
0answers
22 views

Relaxation of the set given by knapsack constraints

A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$. I have a set of points defined as $$ \mathcal{X} = \{x \in \mathcal{Z}^n_{+}: w^{\top}x \...
1
vote
1answer
50 views

Finding a zero of a linear function inside a convex set

Suppose I am given a linear function $F:\mathbb{R}^n\to\mathbb{R}^k$ and a non-empty convex set $K$ which is given as the intersection of half planes. Is there any standard easy method for finding a ...
2
votes
0answers
60 views

Can strong duality for linear programming be viewed intuitively?

Is there a somewhat intuitive way of understanding strong duality in linear programming? I do understand weak duality quite well since it pretty much follows from how the dual problem is defined but I ...
0
votes
1answer
26 views

Optimization problem with variable order and median constraints

I want to solve the following optimization problem: (over $x_1,\dots,x_n,\beta$, where $n,c$ are constants) $$ \max \sum_{i=1}^n x_i (n-i)\\ \text{s.t. } \sum_{i=1}^n x_i =1, \\ x_1\leq \dots\leq x_{...
2
votes
1answer
41 views

Solving a linear program with simplex algorithm, matrix not full rank

I have that matrix named A: \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&-2&0&1&0 \\ 2&4&0&0&1 \end{bmatrix} I need to solve the LP : $$ \min: -x_1 - ...
2
votes
1answer
25 views

simplex algorithm help for continuing in case of $\lambda \equiv 0$

Is it possible that while the simplex algorithm is working, we get a lambda $$ (Ax < b, \max c^T x )$$ $$ \lambda_B = c^T A^{-1}_B $$ with only zeros in it ? if so what does it would represent/ ...
3
votes
1answer
26 views

linear program, why is there an outgoing arc such that $ d(s,v) = w(s,v)$

If any other information is needed, please feel free to ask me. I'm beginning my learning in graph theory and in optimization. Let's call $D = (V,A)$ a directed graph. $w : A \to \mathbb R$, arc ...
1
vote
1answer
40 views

How to find the solutions of a LP problem?

So i have this LP problem: And i need to find the optimal solutions of x1 and x2. On the answer sheet it states that x1=a and x2=0. Now i was thinking of doing it this way: x1+ax2= a then x2=1-...
0
votes
0answers
47 views

How to convert a minimization problem to maximization problem and vice versa

So i have this LP problem that can be transformed into Now thanks to previous users I know that to transform min to max all i need to to is multiply the objective function by -1 But say i want to ...
0
votes
1answer
33 views

Inequality of distances in a graph

Certainly it's obvious but I can't catch the reason behind it. Why do we have : Let $D= (V,A)$ be a directed graph, $w:A \to \mathbb R$ be arc weights and $s \in V$. Denote with $d(s,v)$ the ...
0
votes
0answers
21 views

How to find the optimal values of a dual problem.

So i have this question with this answer and I am not sure if the answer sheet is wrong. I have no problems getting to the dual. However the answer sheet states that y1=18.75 and y2=26.25. I get ...
0
votes
1answer
16 views

How to solve a dual LP problem with three variables?

Given the LP problem I know that the dual will be I know that the optimal value of the LP problem is 7.5 and that the values of x1 and x2 are respectively (0.5,3). However I am not sure how to ...
0
votes
0answers
31 views

Finding the value of variables in optimization problems

So i have this LP problem: The variables are x1 and x2 (like x and y). max 3x1 + 2x2 : 2x1 + x2 ≤ 4 −2x1 + x2 ≤ 2 x1 − x2 ≤ 1 x1 ≥ 0, x2 ≥ 0 Where the second, third and fourth lines are the ...
0
votes
0answers
16 views

stochastic optimisation of asset allocation over time

I have a problem where I'm trying to optimise the allocation of funds between a number of projects $P_1, \cdots, P_M$, each of which has an objective $O_1, \cdots, O_M$. Not only this, but I have an ...
0
votes
1answer
96 views

Lagrange multipliers and the Simplex Algorithm

I am trying to understand the Simplex Algorithm from a gradient perspective, and I am wondering if anyone knows of a method for determining the variables that should both enter and leave the basis of ...
0
votes
0answers
29 views

The linear program for widest path or maximum capacity path problem.

I have to give the linear program for the widest path problem or maximum capacity path problem which gives the path where the greatest flow is achieved. I thought of solving it as a Max Min problem. ...
1
vote
0answers
30 views

Convex Hull of Rational Polyhedra, intersected with whole numbers

I am currently reading into polytope theory, and stumbled upon the following proposition, which I do not really understand: Let $$ P = \{ x \in \mathbb{R}^{k+l} \mid Ax\leq b\} $$ be a rational ...
0
votes
0answers
53 views

Linear programming - removing variables that do not contribute to a solution and adding new ones

Considering the linear program: \begin{equation} \begin{matrix} P_1\hspace{10pt} \displaystyle \min_{x_i} & \sum_{i=1}^{10} {c_ix_i\hspace{20pt}} \\ \textrm{s.t.} & \sum_{i=1}^{10} A_i x_i ...
1
vote
1answer
167 views

Prove that this linear programming problem is bounded by $O(k^{1/2})$

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems: $$\begin{array}{ll} \text{minimize} &...
0
votes
2answers
61 views

Linear programming - value of non-basic variables for the solution of a non-standard linear program

Considering this non-standard linear program: \begin{equation} \begin{matrix} \displaystyle \min_x & c^T x \\ \textrm{s.t.} & A x & = & b \\ & x_i & \geq & 0 & & ...
0
votes
0answers
31 views

Dual of 0-1 integer program

I have worked with LP & IP with solvers like Gurobi and CPLEX. To play around the processes of encoding some practical problem, I am learning how to construct a dual LP from https://en.wikipedia....
0
votes
1answer
84 views

Linearization of logical AND of binary & integer decision variables in the IF condition

I want to linearize following If-else constraint with many logical AND of binary & integer decision variables in the if condition. $if(x_{i,k}=1\;AND\; x_{j,k}=1\; AND\; s[i]\leq s[j]\; AND\; ...
2
votes
0answers
38 views

Warm start a simplex algorithm using a feasible solution

I've been searching a lot for relevant answers to my question. However, I was unable to find a problem formulation with satisfactory answers that would help for my problem. In a nutshell, I would ...
1
vote
0answers
30 views

Transforming a linear constraint. [duplicate]

I have two variables $x$, and $y$. That are related by $Bx=y$. There is also a linear inequality constraint on $x$: $Ax \leq b$. Is it possible to write down the feasible set of $y$ as a linear ...
0
votes
0answers
75 views

Transportation problem in linear programming

It is given the following transportation problem. I can solve it when the cost is increased, but I don't understand what is the change in the model when the transport cost is reduced. Problem: It ...
0
votes
0answers
55 views

How to linearize logical AND constraint in linear programming?

I want to implement " if($x_{i,k}=1$ AND $x_{j,k}=1$) then $p[j]\geq p[i]$ " as a linear constraint. Where $x_{i,k}$, $x_{j,k}$ are binary decision variables and p[i], p[j] are integer decision ...
1
vote
1answer
31 views

CPLEX candidate solutions ignore lazy constraints

Whilst generating lazy constraints through my custom IloCplex.Callback.Function, I encounter the following behaviour: After identifying ‘valid’ lazy constraints A, for one candidate X my heuristic ...