Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-programming]

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

1
vote
2answers
46 views

Linear program with absolute values in the objective

I know that if there is a absolute values in Linear Programming problem, i.e. $min \sum_{i} c_i|x_i|$ s.t $Ax \leq b, x \geq 0$ > then, I can change $|x_i|$ into new variables such as $|x_i| = x^{+...
0
votes
2answers
94 views

Find an optimal solution to a linear program in $O ( n \log n )$

Problem: Given $c \in \mathbb { R } _ { + } ^ { n } , a \in \mathbb { R } _ { + } ^ { n }$ and $\gamma \in \mathbb { R } _ { + } ,$ design an algorithm which, in $O ( n \log n )$ operations, computes ...
1
vote
2answers
43 views

Minima/Maxima of a ILP over any compact set

I am reading this paper "Lagrangian Relaxation for integer programming" by A.M. GEOFFRION. In the paper, to prove one of the lemmas authors use the theorem that "minimum value of a linear ...
0
votes
1answer
30 views

Adding $\lambda\cdot d$ to a constraint. How does the optimal solution change?

We are give a linear programm in standard form. Given $A\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ with Rank$(A)=m$ and $B$ a basis whos basis solution is optimal. Now the right side of the constraint $Ax=...
0
votes
0answers
31 views

Using Farkas Lemma to deduce $0^Tx<-1$

Given the polyhedron $P=\{x \in \mathbb{R}^n\ : Ax\leq b\}$ for $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$ and a vector $w \in \mathbb{Z}^n$. Now consider $\hat{P} = \{x \in P : w^Tx \leq \...
1
vote
0answers
34 views

MIP programming for fairness

I have a MIP model that allocates 24 rides between 6 drivers (with many constraints irrelevant here), and an important part of my objective is splitting the rides fairly. The easiest implementation ...
0
votes
1answer
28 views

duality theorem for homogeneous system

hi there what is dual of a homogeneous system? Primal: $$\text{Max}\ cx $$ $$ Ax \le 0 $$ Dual : $$Min\ 0 $$ $$A^{T}y=c$$ $$y\ge 0$$ but what does it mean $Min\ 0$ in dual problem?
2
votes
0answers
37 views

Work the least possible without ever seeing your coworkers, or minimize the sum of two coprime numbers such that their product is at least $n$

The solution to the associated continuous problem: $$ \min_{(x,y) \in S} x+y $$ where $$ S=\left\lbrace (x,y)\vert n \leq xy\right\rbrace $$ Is $x=y=\sqrt{n}$. There is an associated problem where: ...
2
votes
1answer
36 views

Removing non-negativity constraint in a linear programming problem

Let's say I have a linear programming problem, i.e. \begin{array}{rl} \text{maximize} & c^T x \\ \text{subject to} & {\bf A} x \le b \end{array} without the non-negativity constraint on $x$ ...
1
vote
1answer
31 views

what does this symbol mean in terms of optimization problems?

I have a study https://drive.google.com/file/d/1vcgc1iDE7O8UlPHNMW3Ld18QzEP8N5Zg/view?usp=sharing I want to understand the meaning of this symbol symbol
2
votes
1answer
48 views

What is the computational complexity of linear programming?

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?
1
vote
1answer
34 views

Linearizing a constraint containing a root square expression

We are working on a combinatorial optimization problem. In order to solve it using CPLEX, we need to linearize the non-linear constraint stated in the following. Let $p_i, i \in I$ denotes a set of ...
0
votes
0answers
28 views

Constrained LP in two variables

Suppose we have the following constrained LP $$\max_{y} \min_x c^Tx $$ $$\text{s.t} \qquad x \geq a + b y^T x $$ Since now $y$ just appears in constraint, can we change the above LP somehow such ...
0
votes
1answer
40 views

Find minimum sum over absolute values of linear functions

I want to find the minimum value of an expression like $$ \lvert -1 + 2x + 6y + 14z \rvert + 2 \lvert -1 - 3x - 7y - 15z \rvert + 3 \lvert +1 + x \rvert + 4 \lvert +1 + y \rvert + 5 \lvert -1 + z \...
0
votes
1answer
29 views

Stiemke's Theorem

Stiemke's Theorem: Only one of the following statements are true: (a) $Ax\leq 0$ has a solution $x$. (b) $A^Ty=0$, $y>0$ has a solutions $y$. I'm trying to understand this theorem. Look at the ...
0
votes
1answer
31 views

Chebyshev center of a polyhedron: nonnegativity issue

Let us have a polyhedron, defined by the inequalities of the form: $$ \mathcal{P} = \{ x \ | \ a_i^T x \leq b_i, \ i=1,\ldots,m \} $$ Here on page 19, the way to calculate Chebyshev center is given ...
0
votes
1answer
29 views

Terminating condition of Simplex Method - Stronger termination conditon

My textbook states "If there are no negative values in the top row of the Simplex tableau, then we have reached optimality" That seems intuitive enough. However, I am wondering if the following, ...
0
votes
1answer
23 views

First-order necessary condition for a local minimizer

Let C be a convex set in Rn, and let f be a differentiable function on an open set containing C . First-order necessary condition for a local minimizer : If x∗ ∈ C is a local minimizer of f on C, then ...
0
votes
1answer
34 views

Linear programming/seeing feasibility and unboudedness

Consider the dual linear programming problem and its simplex dually feasible table: $$\begin{array}{|c|c|c|c|c|c|c|c|}\hline -4& 0 & 1&5&16&0&4&0 \\ \hline -12& 0 &...
1
vote
1answer
37 views

Calculating number of bases that lead to basic feasible solution

Let $P = \{x \in R^n | Ax \geq b \}$. Suppose that at a particular basic feasible solution, there are $k$ active constraints with $k>n$. Is it true that there exists exactly $C(k,n)$ bases that ...
0
votes
1answer
40 views

Scheduling Problem

My boss asked me to come up with a presentation that recommends how many hires she would need to support our tests. I have data that shows the number of tests per day. Assuming one worker per test, ...
0
votes
0answers
39 views

Is the following knapsack modelling correct (with additional constraints)

I was wondering whether the following knapsack ILP is modelled correctly. The model is as follows: The knapsack model has a vector $\mathbf{w} = (w_{1}, \cdots, w_{j}, \cdots, w_{n})$, which contain ...
2
votes
1answer
66 views

Find the Dual of a Primal Linear Programming Problem

Consider the problem $$\text{min}_{x\in\mathbb R^n}\lvert Ax-b\rvert,$$ where $A$ is a $m \times n$ matrix and $b\in\mathbb R^m.$ Rewrite the problem into the form$$(P)\qquad \text{Minimize }\lvert z\...
1
vote
1answer
17 views

Is this the most efficient way to rearrange a linear programming objective with an absolute for lpsolve?

If linear programming is to be used to solve an objective function which contains absolutes then the absolute terms have to be rewritten using extra values, for example, the trivial objective "...
0
votes
0answers
26 views

Linear programming problem minimization change problem

minimize $max ${x1,x2} subject to $2x1+5x2<=9$ $x1+3x2<=5$ $x1>=0$, $x2>=0$ show that both are same and give reason minimize t subject to t>=x1 , t>=x2 $2x1+5x2<=9$ $x1+3x2<=5$ ...
1
vote
1answer
60 views

Non degenerate optimal solution in primal <=> non degenerate optimal solution in dual

I was trying to solve this exercise when my primal is $\min c'x$ $s.t: \ Ax=b \ , x \geq 0 $. For the => proof i think i solved it. This helped me a lot. But the reverse, i think is more ...
0
votes
0answers
16 views

Showing Weak Duality

Suppose we have the Linear program max{$c^Tx: Ax \geq b, x \leq 0$}, and thus its corresponding dual is min{$b^Ty: A^Ty \geq c, y \geq0$}. I am trying to prove that weak duality holds and that $b^Ty \...
0
votes
0answers
35 views

Simplex method using two phase [duplicate]

(P) minimize: $z=x_1+x_2$ subject to : $$\begin{aligned} x_1 + 2 x_2 &\geq 4 & &\text{Eq.1} \\ 2x_1 + x_2 &\geq 6 & &\text{Eq.2} \\ -x_1 + x_2 &\leq 1 & &...
0
votes
1answer
92 views

question about linear programming minimization

(P) $\min z=x_1+x_2$ subject to : $ x_1+2x_2 \geq 4$ ( equation 1) $2x_1+x_2\geq6$ (equation 2) $-x_1+x_2\leq1$ (equation 3) $x_1>=0 ,x_2\geq0 $$ $ I'm trying to solve this using two-...
0
votes
1answer
28 views

complex problem turning logical conditions into linear expressions

I'm trying to add a logical condition constraint into a linear expression on puLP in python. I have translated them by myself and coded them, but the solution is infeasible, which should not be the ...
1
vote
1answer
23 views

(Existence part of) Neyman-Pearson via weak-* convergence

I would like a ask whether there is any statistical reference containing the following functional analytic argument for the existence part of Neyman-Pearson: Let $(R, \mathcal{F}, \mu)$ be a measure ...
0
votes
2answers
75 views

IF a == b, then c = 1, else 0. How to turn this to a linear expression? [closed]

I want to turn the following condition into a linear expression: If a == b, then c = 1, else 0. How should I transform this into a linear expression? Thanks!
0
votes
1answer
33 views

Degeneracy Condition

I understood that when plotting the feasible area there had to be an intersection with more than two lines. In the case of: $$\text{Max } z=2x_1+x_2$$ S.T $$ \begin{cases} 4x_1+3x_2\leq 12\\ ...
-1
votes
1answer
27 views

Basic Columns In Simplex

On the following note it says that if a non basic column has no positive coefficient so this is the case of unboundedness. What non basic column refer to?
2
votes
1answer
47 views

Stochastic programming: Is the linear program over the vertices the same as over the simplex?

Suppose we have a random variable $W$ with probability distribution, $\Pr(W = w) = p_w \in [0,1], \quad w \in I = \{1, \ldots n\}$ Consider the maximization problem: $$\max\limits_{w \in I} \...
0
votes
2answers
72 views

How to calculate minimax value with simplex method?

For the LP problems with only inequality constraints, I know how to use simplex method to give an optimal solution. However, when I want to calculate the minimax value, how should I use the simplex ...
0
votes
1answer
30 views

Convexity Proof for $\mathbb R ^n \backslash A$

I need to tell if it is true or false and prove that given $A$ a convex set, $\mathbb R^n$ \ $ A $ is never convex. So far I get that considering $p,q \in \mathbb R^n$ convex, $\lambda p + (1- \...
0
votes
1answer
30 views

Solution of a LP, give the probabilities of a mixed strategy of a zero sum game [closed]

Given a zero sum game like this one : \begin{array}{c|rrrr} & A & B \\\hline X & 4 & 3 \\ Y & 2 & 5 \\ \end{array} and the given LP : minimize $ x+y $ s.t. : $x \geq 0, y \...
1
vote
0answers
96 views

Dual of the barrier transformed linear program $\min_{x \in \mathbb{R}^n} \left\{ c^T x - \mu \sum_{j=1}^n \log(x_j) : Ax = b; x \geq 0 \right\}$

Dual of the following linear program \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & c^T x \ -\mu \sum_{j=1}^n \log(x_j) \\ \text{subject to }\quad & Ax = b\\ & x \geq 0 \ , \...
1
vote
2answers
44 views

Linear program geometry

I’ve tried to solve a question in my homework, and I don’t really know what to do. In the problem a polyhedron is given and I need to build the set of constraints that defines this polyhedron. The ...
2
votes
2answers
40 views

Strict inequality logical implication in optimization problems

I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks. One part of the implication is easy $ y \leq Mx$. The ...
0
votes
1answer
17 views

Linear programming with what I think has 3 variable. I need to plot a graph of the constraints too. [closed]

I have a question. A refinery gets oil from three wells. Each wells provides oil with a certain amount of lead and iso-octane. The blended product must contain a maximum of 3.5% lead and a minimum of ...
1
vote
2answers
43 views

Corresponding LP problems to zero sum games

Given a zero sum game like this one : \begin{array}{c|rrrr} & A & B \\\hline X & 10 & 3 \\ Y & 5 & 9 \\ \end{array} how do you find an equivalent linear program ? I think ...
0
votes
0answers
30 views

Products of k/l-gons

For $k \geq 3$ let $P_k = conv\{(\cos\frac{2\pi\cdot i}{k}, \sin\frac{2\pi\cdot i}{k})\ |\ 0 \leq k < i\}$ be a regular $k$-gon in $\mathbb{R}^2$. We want to look at product $P_k \times P_l$ in $\...
1
vote
1answer
118 views

Help in understanding proof of lexicographic rule's role in terminating the simplex method

Theorem: The simplex method terminates as long as the leaving variable is selected by the lexicographic rule in each iteration. I am reading through the proof of this theorem and understand all but ...
0
votes
2answers
39 views

confused in linear property?

I have a system $$y(t)=3x(t)+2\cos(\pi t/3)$$ I am confused if this function/system is linear or not? As if only we had $y=3x$, it would be definitely linear but now due to cos term, scenario ...
0
votes
1answer
34 views

Why do we need (or use) identity matrix while proceeding simplex method

I've been studying for operational research recently.I did comprehend how the algorithm works.However I could not figure out why do we need identity matrix and why do we need to create it while ...
1
vote
0answers
22 views

Is this dual linear program correct? If so, how would I interpret its variables/contstraints/optimum?

I'm confronted with the following situation: A company has $5$ employees (conveniently numbered from $1$ to $5$). Each employee is paid at a fixed rate per task completed. The company also has an ...
2
votes
1answer
34 views

Linear programming: redistributing bikes at the end of the day

I'm not sure how I can approach this problem. I need to state the problem before asking my questions. Problem. Suppose a city has many bike stations. You can rent a bike and turn it back at any ...
-1
votes
2answers
61 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...