Questions tagged [linear-programming]

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

0
votes
0answers
3 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
0answers
15 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
2answers
44 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
21 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 ...
1
vote
1answer
86 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
0answers
22 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. ...
0
votes
0answers
27 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 ...
0
votes
0answers
16 views

min max theorem proof, equivalence of duality problems, how to do it?

I'm trying to do the min-max theorem's proof. In it, I need to prove the following equivalence of linear program (one is the dual of the other): $$\max\{ x_0 \mid \textbf{ 1 } x_0 - A^T x \leq 0, \...
0
votes
0answers
44 views

Linear programming over integers mod 2, expressing function as sum of two

Let $h=a+\ell+1$ and define $$ f(a,\ell;u_2,u_1,\rho,n) = \frac{h^2}2 u_2 +h(a+\frac12)u_1+\frac{a(a+1)}2 \rho+n$$ where all the variables are integers, and such that $u_1=u_2 \pmod{2}$. Such $f$ is ...
0
votes
1answer
50 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\; ...
0
votes
0answers
46 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
24 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
31 views

Distributing a shift evenly amongst employees

For employee scheduling, I am writing a MIP. I am trying to distribute the shifts amongst the employees with the same skills as even as possible. e.g. ============================= Three employees ...
2
votes
0answers
26 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
26 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
1answer
44 views

How can I linearize this IF-THEN constraint? [duplicate]

Let, $m=1,2,\cdots,M$ $b_{m}$ is a binary variable $c_{m}$ is a continuous variable I have an IF-THEN constraint like this IF $a_{m}=1$, THEN $f_{m}> 0$ IF $a_{m}=0$, THEN $f_{m}=0$
0
votes
0answers
39 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 ...
4
votes
0answers
94 views

Book recommendation to study topics of Linear Programming for self study

I need some reference book suitable for self-study with many solved examples and solutions preferably for exercise questions for following study. Need basic honours undergraduate level text , ...
0
votes
1answer
797 views

Formulation of mutually exclusive condition

So I have two integer variable and they can be one of the following $x=0, y=1$ $x=1, y=0$ $x=2, y=0$ how can I formulate this as an integer program? I've gotten $x + y \le 2$ and $y \le 1$ but ...
1
vote
1answer
25 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 ...
0
votes
0answers
35 views

Optimization problem - please help a man in need [closed]

I started studying optimization methods and I ran to this task. In a town there are N friends who like to gossip. One day each of them found out one gossip. How many calls do they have to make at ...
0
votes
0answers
17 views

Simplex method interactive tutorial/tableau builder

Does anyone know of any online applets or maybe free software that allows you to build simplex tableaus interactively? I am not after a calculator that just gives all the tableaus and the solution, ...
-2
votes
1answer
22 views

Why do we call Basic solution (linear programming), any reason for that ??

I'm just curious that why do we call such a solution with some property, a "basic" solution. I would like to know the background. Thank you in advance.
0
votes
0answers
24 views

Minimizing a Linear Function Over a Halfspace

I'm currently studying convex optimization using Boyd & Vandenberghe's textbook. The exercise problem that I'm having trouble with is the exact same as the one here. I'll write it out: $$\begin{...
1
vote
0answers
46 views

When is the simplex method slower than the ellipsoid algorithm?

In an undergrad class on linear programming, we learned about the simplex and ellipsoid methods for solving linear programs (LPs). I know that the simplex method is generally faster than the ellipsoid ...
0
votes
1answer
21 views

Linear program with $\pm 1$ constraints

I am trying to formulate a constraint as follows ($X, Y, Z$ are either $-1$ or $1$): If $Z$ and $Y$ both equal $-1$, then $X$ must be $1$. But, if either $Z$ or $Y$ are not $-1$, then $X$ can be $-1$...
4
votes
1answer
37 views

How is $x = -\text{sign}(c_i)e_i$ the solution to minimize $c^T x$ subject to $\|x\|_1 \le 1$?

From Convex Optimization by Boyd & Vandenberghe: $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & \|x\|_1 \le 1\end{array}$$ Let $i$ be the index such that $\|c\|_{...
0
votes
1answer
31 views

Optimization problem for maximum profit

I have to write a linear program for the following problem: We have three products that are made in a factory: A, B and C, we are given the amount of energy every product needs (A ~ 1kWh, B ~ ...
0
votes
0answers
25 views

Assignment problem using Hungarian method

There are5 jobs to ne assigned one each to five machine and associated cost matrix is as follows Machine 1. 2. 3. 4. 5 Job. A [11 17 8 16 20] B [9. ...
0
votes
2answers
35 views

Categorize my constraint [closed]

Is the following constraint linear? $$\lambda_1=\alpha_1 q^2+\varepsilon$$ $\lambda$ is a 1x8760 vector which is also a decision variable. $\alpha$ is just a number, which is also a decision ...
0
votes
0answers
36 views

is this optimization problem linear programming?

Is the following problem linear programming? (Bold font = vector) if not, what kind of problem is it? The decision variable is lambda and alpha. Epsilon is constant. q is an input vector, with ...
0
votes
1answer
821 views

condition for having a positive solution to a linear equation.

Let $Y$ be a member of $\mathbb{R}^m$. I need a necessary and sufficient condition on a $n\times m$ binary matrix $A$ for having a solution to the linear equation: $$AX=Y$$ Such that $X_i\geq 0$, $\...
0
votes
2answers
1k views

Linear Programming Word Problem With 3 Variables

A company makes three types of candy and packages them in three assortments. Assortment I contains 4 sour​, 4 lemon​, and 12 lime ​candies, and sells for ​$9.40. Assortment II contains 12 sour​, 4 ...
1
vote
1answer
25 views

Modelling a range constraint based on a value

I'm trying to model a constraint based on a range. I have a lp variable $x_1$ with range $[0,60]$, and a binary variable $y_1$. $y_1$ must be $1$ iff $x_1$ belongs to the range $[25,35]$. How do I ...
1
vote
1answer
33 views

Constraint formulation that include consecutive values in an optimization problem

I am currently lost in finding a way on how to mathematically formulate a constraint within the following problem: I want to allocate some water tanks locations within a network, which size will vary ...
0
votes
0answers
41 views

Let $P$ be $\{\text{min}\ cx | Ax = b, x \ge 0\}$ and show $(y^*)^T(\bar{b} - b) \le c^T(\bar{x} - x^*)$

Let $P$ be the linear programming problem $\{\text{min}\ cx | Ax = b, x \ge 0\}$, where $x \in \mathbb{R}^n$, $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$. Assume $P$ is feasible and bounded. ...
1
vote
1answer
31 views

Extreme points of a polyhedron and convex combination

Problem: Let $x \in P, P$ a polyhedron. Show that if $x$ cannot be written as a convex combination of other points in $P$, then $x$ is an extreme point of $P$. Proof: We see that in $x$, (at ...
2
votes
2answers
881 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
2
votes
1answer
895 views

Plotting multiple planes with three variables in 3D using MATLAB

I couldn't figure out, how I could plot three different equations with three variables, namely x,y and z in MATLAB or any other Mathematical Softwares. I know that there's a way we could plot multiple ...
1
vote
1answer
13 views

how do we know from a degenerate simplex tableau of an LP problem if the current basic feasible solution is optimal?

(simplex method) In degenerate cases, the current basic feasible solution with positive reduced cost coefficient can also be an optimal solution (in non-degenerate cases, the optimal solution is ...
1
vote
1answer
30 views

Optimize concave function divided by a linear function

If I divide a monoton concave upper and lower bounded function by a linear function, whould the result be concave? Or even easy to optimize?
0
votes
1answer
25 views

Complicated transporting problem.

In the following problem, goods will be transported from farmers to stores. I know how to minimise the transport costs in such problems. The complication comes because the goods have to go to some ...
0
votes
0answers
24 views

duality in linear programming for cost minimization of forest plantations

I am trying to use duality in linear programming to minimise the cost for highest possible revenue. Forest plantations have 2 species (pine and eucalyptus), i have 3 cost variables (land,labour and ...
1
vote
1answer
28 views

Simplex method problem

We consider the constraint equation is $Ax=b$ where $A$ is a $m \times n$ matrix. I know that in phase one of simplex method, we should find a vertex/corner of feasible set. I'm confused that why ...
1
vote
1answer
19 views

Gradient-based interpretation of the simplex algorithm

The simplex algorithm iterates from vertex to vertex of the convex polytope that bounds the feasible region of the constrained optimization problem, such that each iteration of the algorithm moves ...
0
votes
0answers
41 views

Understanding the steps of Karmarkar's algorithm

I am working through Karmarkar's seminal paper [0] and came across something I didn't quite understand. In section 2.3, Description of the Algorithm, he explains how to calculate the next point. The ...
1
vote
1answer
46 views

Determining whether a polyhedral cone is a subset of another polyhedral cone

Let $A, B \in \mathbb{R}^{n \times n}$. The polyhedral cones of $A$ and $B$ are given by $$\mathcal{C}_A = \{ x \in \mathbb{R}^n : x = A \lambda, \mbox{ where } \lambda_i \ge 0 \mbox{ for all } i = 1, ...
1
vote
0answers
19 views

How to format the dual to this linear programming problem?

Minimize $$2y_1 -3y_2 + 4y_3$$ subject to $$8 y_1 -y_3 = 50\\ 6y_2 +y_3 \le 60\\ y_1, y_2 \ge 0, -15 \le y_3 \ge 0$$ The problem is to write the dual. I end up with Maximize $$50x_5 - 60x_3 + 15 ...
0
votes
1answer
888 views

What to do when ratio test gives same result for two different variables? (in Linear Programming)

In simplex algorithm, I applied the ratio test to find the leaving variable but it gave same result for two variables. Should I choose one of them and calculate the objective function or calculate for ...
0
votes
1answer
21 views

Artificial Variables in Two Phase Simplex Method

I am coding a Two-Phase Simplex solver, just as a part to improve my programming skills. I am testing this program on many LP problems, and I found one where it doesn't work as expected, so I want to ...