Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
2
votes
3answers
21 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
24 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
22 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
26 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
23 views
LP - Simplex - Two Phase Method - Multiple Solutions
Given the following lp:
MIN Z = x1 + 2x2 + 3x3
s.t.
x1 + x2 + x3 = 1.0
x3 <= 0.8
x2 = 0.5
x1 >= 0.0
x2 >= 0.0
x3 >= 0.5
The single optimal solution ...
0
votes
0answers
23 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
13 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
25 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
44 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
24 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
26 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
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
35 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
55 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
26 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
36 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
33 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
42 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
85 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
36 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
30 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
32 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
26 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
36 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
32 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
1
vote
1answer
43 views
What is the computational complexity of linear programming?
I am looking for the computational complexity of solving a linear problem with n variables and m constraints.
1
vote
1answer
26 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 \...
-1
votes
0answers
11 views
If linear inequality system S(x,y) is feasible, can we prove S(f(x),g(y)) feasible? Given f, g are linear functions.
What I'm trying to do is to decide if a system is feasible after multiple linear transformations. If the above statement is valid then I just need to solve the initial system to get the answer.
0
votes
1answer
26 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
28 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
26 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
20 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
31 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 &...
