Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
3,243 questions
1
vote
1answer
22 views
Show that a set $\mathcal U$ is convex
Consider the set
$$
\mathcal{U}\equiv \{U\in \mathbb{R}^K: T(U)< T'(U)\}
$$
where $T$ and $T'$ are linear functionals of the vector $U$.
I want to show that $\mathcal{U}$ is convex using the ...
1
vote
1answer
17 views
Subgradient procedure for lagrangian relaxation of GAP
I'm trying to solve the general assignment problem by relaxing the capacity constraint and applying the subgradient procedure.
GAP (from here):
Relaxation (same source as above):
Subgradient method ...
0
votes
0answers
24 views
Proving equivalence with Farkas lemma
The problem I am trying to solve:
trying to show that the two systems are equivalent.
$$\exists x : Ax=a$$
$$Bx \leq b $$
second system:
$$\nexists y,z: y^TA+z^TB=0$$
$$y^Ta+z^Tb<0$$
$$z\geq 0$$...
3
votes
1answer
36 views
Optimise allocation to minimise variance
Background
I am trying to allocate customers $C_i$ to financial advisers $P_j$. Each customer has a policy value $x_i$. I'm assuming that the number of customers ($n$) allocated to each adviser is ...
2
votes
1answer
22 views
Knowing that a feasible solution exists and has a finite optimal solution
I have the following linear programming problem:
constraints:
$x_1,x_2,x_3\geq200$
$0.45x_1+0.41x_2+0.5x_3 \leq 960$
$x_1+x_2+x_3 \leq 2000$
$ x_2+x_3 \leq x_1$
objective functions:
max $0.35 ...
0
votes
1answer
44 views
Where do the points (-1,3) and (2,1) come from?
I now understand how the green area is obtained from the set definition below in point 2, but how is that set itself constructed? More precisely, where do the points $(-1,3)$ and $(2,1)$ come from?
0
votes
3answers
40 views
Draw region given set of points.
Can someone explain how
$$\{\mathbf{x}\in\mathbb{R}^2 \ | \ \mathbf{x}=\begin{pmatrix}2\\2\end{pmatrix} + \lambda_1\begin{pmatrix}-1\\3\end{pmatrix}+\lambda_2\begin{pmatrix}2\\1\end{pmatrix};\...
1
vote
1answer
22 views
Simplex Method with Nontrivial Initial Solution
I have a linear program with the following tableaux:
\begin{array}{crrrrrr|l}
& x_1 & x_2 & s_1 & s_2 & s_3 & P & rhs \\ \hline
& 67&...
2
votes
0answers
22 views
Multiple Sensor Pointing Optimization: Formulation and is MILP the correct approach
SourceDataFile
So i am attempting to optimize the following pointing problem. I have a set of sensors (cameras) and a set of targets. Each camera can be oriented directly at one one target, but based ...
0
votes
1answer
21 views
A standard way to reduce a k-SAT to 0-1 Integer Linear Programming
I was searching for a standard (a published paper) for which it reduces a k-SAT to a 0-1 ILP (Integer Linear Programming), but couldn't find any :(
I know how to reduce a SAT problem to an ILP ...
3
votes
1answer
35 views
+50
Formulation of SVM optimization problem
I need help in verifying/understanding a step in formulating an optimization problem used for support vector machines (though this question doesn't need any background in SVM). Consider a bunch of $m$ ...
0
votes
0answers
28 views
Linear Programing For Forest Management
The question I am working on is as follows,
You are in charge of managing a $200,000$-acre forest. Of these $200,000$ acres, $80,000$ can only grow pine and $40,000$ can only grow aspen. The ...
2
votes
1answer
46 views
Optimal Strategy in a money compounding model where one's interest is only consolidated at a fee
Say I have my main account with $ \$ 10000$ that gains interest at a rate of .1% a day. The interest collects in a separate account and I have to pay a certain fee, say $\$1$, to consolidate this ...
1
vote
1answer
33 views
Linearize $(a = cst) \implies (b = 0)$
Suppose I have two integer and non-negative decision variables $a$ and $b$ in a linear program and a constant $c$, how can I express with linear inequalities that $(a = c) \implies (b = 0)$?
You can ...
0
votes
1answer
81 views
Is there any way to linearize $x-x^2\leq 0$?
I am trying to solve an optimization problem.
The objective function and all constraints of this problem are linear except $x-x^2\leq 0$.
Is there any way to linearize $x-x^2\leq 0$, where $x$ is a ...
0
votes
1answer
9 views
linear programming - variable satisfies non-zero lowerbound or zero
I have a linear programming problem of the form
$\max_{x_1,\ldots,x_N} \mathbf{c}^T\mathbf{x}$
such that
$\mathbf{Ax}\leq \mathbf{b}$ and
($x_{\text{min}}\leq x_i\leq x_{\text{max}}$ or $x_i=0$)
...
1
vote
1answer
81 views
Can I do statistical analysis over a MILP problem?
I'm trying to solve a delivery problem which involves transportation of goods from a set of sources to a set of destinations ...
0
votes
0answers
6 views
simplex $B^{-1} \cdot A_j$ tableau interpretation
In an iteration of the simplex tableau implementation, what is the interpretation of the columns $B^{-1} \cdot A_j$ underneath each variable $x_j$?
0
votes
0answers
21 views
About the optimal solution to an Integer-linear-programming (ILP) problem
Is it true that the optimal solution to an ILP problem must be one of the neighboring points of the points on the boundaries of the corresponding relaxed LP problem? Is so, how to prove it?
That is, ...
2
votes
3answers
26 views
Finding numerical values to an equation describing a hyperplane or a plane (any software suggestion?)
The following equation
$$0.27a+0.1b+0.13c=70$$
can admit many solution. Is there any software/methods I can use so that I can have a large list of all the possible numerical solutions to this equation?...
1
vote
0answers
28 views
What is the meaning of Motzkin's theorem?
Theorem: Let $A$ and $C$ be two matrices. The system of linear inequalities $Ax<0$ and $Cx \leq 0$ has a solution iff the following equation in $\lambda$ and $\mu$ does not have a solution$$A^T \...
2
votes
1answer
27 views
What are optimality conditions?
My question is rather general and in advance I appologize for not being precise enough, which is very likely. It concerns the matter: what do people understand by optimality conditions?
Suppose we ...
1
vote
0answers
32 views
Sensitivity of each part of the objective function to each constraint
Suppose that we have the following linear optimization problem:
$$\min\ 2x_1+3x_2$$
s.t.
$$x_1\le100\ :a=a_1+a_2$$
$$x_2\le50\ :b=b_1+b_2$$
$$125-x_1-x_2=0\ :c=c_1+c_2$$
$$x_1,x_2\ge0$$
In ...
0
votes
0answers
26 views
Integer Linear Programming with Expectation of Random Variables
I'm looking to get pointed in the right direction with regards to research on a particular (Stochastic) Integer Linear Programming case. I've been looking into stochastic, chance-constrained, and ...
0
votes
1answer
25 views
How to get $B^{-1}$ from simplex table?
In each iteration of the simplex method the table has the form:
I'm reading "Introduction to linear optimization" by Bertsimas and given the following example of a linear program:
An optimal table ...
4
votes
1answer
28 views
Probabilistic interpretation of optimality gap in Integer Program
Suppose I have an integer program model in the form of a minimization. I noticed that Gurobi (my solver) often finds a very good upper bound (i.e., feasible solution) whereas it takes a significant ...
0
votes
0answers
46 views
Linear Program is Surprisngly Infeasible - Trying to Write the Dual
I need to solve the following linear program:
$$\displaystyle{\min_{\bar{X},t}} \hspace{0.1in}t$$
such that:
$$A\bar{X}=\tilde{x} + td$$
where $A$ is $N\times N$ and known, $t$ is scalar, $\tilde{...
0
votes
1answer
25 views
What does it mean when we can't put a particular variable as a basic variable in a LPP?
Consider the LPP of minimizing $z = -2x_1 + x_2$ subject to
$$\begin{cases}
x_1 + 2x_2 \le 6, \\
3x_1 + 2x_2 \le 12, \\
x_1, x_2 \ge 0
\end{cases}$$
First I add slack variables $x_3, x_4$ which ...
1
vote
0answers
27 views
Convex Conjugate of sum-of-max terms
Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a sum-of-max linear terms function:
$$f(x) = \sum_{k=1}^K \max_i\{a_{k,i}^\top x\}$$
where $a$ are the linear coefficients.
I am interested in the convex ...
0
votes
0answers
14 views
Simplify a triple cycle
I'm writing an algorithm which computes the solution for a pretty complex (for me) problem which I found online. I couldn't find a smart solution, so I decided to use the brute force.
BUT
as ...
1
vote
2answers
24 views
How to specify a constraint for an LP when it needs to be related to ONE of two other variables depending on smallest?
So I have a problem where I need to model a LP, but the question specifies a constraint such that x_1 must be at least 40% more than x_2 or x_3
I thought of defining it as x_1 >= 1.4 (min(x_2, x_3)) ...
1
vote
1answer
32 views
Setting up a linear equation of three variables with two equations
For the following question that has appeared in one of my homework questions, I have:
A fisheries laboratory needs to prepare $300$ litres of salt
solution to replenish their tropical tank with salt ...
1
vote
1answer
26 views
Problems with solving the dual problem graphically
I have the following problem
minimize $21x_1-15x_2-16x_3$
subject to $2x_1-5x_2+7x_3\ge2$
$3x_1+3x_2-2x_3\ge-5$
$x_1,x_2,x_3\ge0$
So, I transformed the second constraint to make sure that the ...
0
votes
0answers
57 views
Proof in regression model
Im studying for an exam, i don't have the solution, so I hope some of you guys can help me. I have tried a lot but i can't do this proof.
Here is the task:
Suoppose we have the linear regression ...
2
votes
1answer
37 views
Should Mister Hungerman eat Thai or Mexican?
Mr. Hungerman’s preferences on Thai (T) and Mexican (M) food are given by
$$ U(x_T,x_M) = a x_T + b x_M $$
Let $ p_T $ and $ p_M $ denotes the prices of a Thai dinner and a Mexican dinner,...
0
votes
0answers
23 views
Optimize for a parameter in a function with constraints on other 2 more parameters
I am an applied statistics student trying to solve a problem where constrained optimization is required. I have a function $f(x, p_1, p_2)$ in which $p_1 \epsilon [0,1]$, $p_2 \epsilon [0,1]$ are ...
1
vote
1answer
60 views
Infeasible solution in Duality and Dual simplex method
Currently I am preparing the Linear Programming exam and I've got some issue to solve these problems. Shortly, suppose some linear program: max $C^{T}X$ s.t. $AX \leq b$, where $A$ is $2 \times 3$ ...
1
vote
0answers
23 views
Motivation for Projection definition in polytopes
In the following Projection, Lifting and Extended Formulation in Integer
and Combinatorial Optimization by EGON BALAS polytope projection definitions are given:
Given a polyhedron of the form
$$Q := \...
0
votes
0answers
20 views
what is the relation between projection of a polytope and this polytope?
suppose we have a polytope $P$ in $R^{4}$ and $-1\leq x_{3}\leq 4$ and $0\leq x_{4}\leq 6$, if I replace the upper and lower bound of $x_{3}$ and $x_{4}$ (it depends on the sign of variables $x_{4}$ ...
0
votes
0answers
26 views
How can a semidefinite program be written as a linear program?
I see that they have the same objective function and equality constraint $Ax = b$, but I am having trouble with showing that $Gx \preceq h $ can be written as $$x_1F_1 + \dots + x_nF_n + K \preceq 0$$ ...
2
votes
1answer
21 views
3-connectivity as a set linear constraints
It turns out connectivity of a graph can be expressed as a set of linear constraints. https://www.researchgate.net/post/How_can_I_ensure_graph_connectivity_using_LP_or_MIP_formulation
Giving a vertex ...
0
votes
1answer
12 views
Why is supremum of $ a*u where ||u||_2 < r is r*||a||_2 $ from the Chebyshev center problem?
Recently I've been reading Convex optimization, in the Chebyshev center problem for linear programming, there is a statement that
(1)$$ sup\{a^Tu \ | \ \ \Arrowvert u\Arrowvert_2 \leq r\} = r\...
0
votes
1answer
27 views
Prove optimality of the output of the algorithm
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
0answers
22 views
Looking for systems of linear equations to construct polyhedrons
I am looking for linear equation systems for the construction of standard polyhedra in 3 dimensions. I found another one beside the simple cube, the Cuboctahedron:
...
1
vote
1answer
11 views
What is the characteristic cone of a system with infinite linear inequalities?
Suppose that I have a system of linear equations for a variable $x\in\mathbb{R}^n$:
$$a_i^Tx\ge b_i,\quad i\in I,\quad (1)$$
where $a_i\in\mathbb{R}^n$ and $b_i\in\mathbb{R}$ for all $i\in I$, and $...
1
vote
0answers
37 views
Minimal nonnegative combinations of vectors
Fact: Start with $m$ points $u_1,...,u_m\in \mathbb R^n$. Now pick any $u$ in the cone of $u_1,...,u_m$; that is,
$$
u = \sum_{i=1}^m \alpha_i u_i \text{ for some } \alpha_i \geq 0, \; i = 1,...,m....
1
vote
1answer
48 views
General solution to linear program?
Source of the Problem
The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we ...
1
vote
2answers
38 views
When the smallest subscript rule doesn't find a feasible solution in LP
I've got a Linear Programming problem which is related to Bland's rule a.k.a. the smallest subscript rule.
The problem is as follows:
max $Z = 10x_1 + 12x_2 + 12x_3$
$\quad s.t$
$\quad ...
0
votes
1answer
26 views
Find the equivalent linear program
This is a classic question, its for a homework assignment, I have the solution but I've been breaking my head to understand how to approach the problem.
Minimize $||A\vec x - \vec b||_1$ subject to ...
1
vote
2answers
43 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^{+...
