Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,138
questions
1
vote
0answers
27 views
farkas' lemma and solution
I know that Farkas' lemma certifies feasibility of a system Ax=b x>=0. Now suppose it's feasible. How do I find a solution x and under what conditions on A and b do I know the solution is unique?
1
vote
1answer
50 views
Reading the primal solution from dual simplex tableau
I was following ptrickJMT's video on how to solve a minimization linear programming problem and he did something that I did not understand why it works. He starts with the following minimization ...
0
votes
0answers
30 views
How to get the Values of an given tableau of the simplex algorithm?
I have some problems with some task of an old exam and i hope u can give me a hint or a way to solve those.
Given is the tableau
$\begin{equation}
\begin{bmatrix}
\begin{array}{c|ccccccc}
& ...
4
votes
1answer
67 views
Does every compact (not necessarily convex) set have extreme points?
Let $A$ be a set in a normed vector space. Call a point $p$ in $A$ extreme if there do not exist $p_0, p_1$ in $A$, distinct from $p$, such that $\lambda p_0+(1-\lambda)p_1=p$, for $\lambda \in [0,1]$....
1
vote
3answers
75 views
What are the extreme points of this polytope?
Let $n, k$ be positive integers with $n\geq k$.
Let $P_{n,k}$ be the set of vectors $x$ in $[0,1]^n$ for which
$$ \sum_{i=1}^n x_i = k $$
$P_{n,k}$ is defined by linear equations, so it is a polytope. ...
0
votes
0answers
21 views
Answering questions about a linear system with constraints
Normally, in solving problems with linear systems, one is given a system of constraints and wishes to find a solution, but in my case I am given a solution and want to find a system for which the ...
0
votes
1answer
32 views
What does it mean to set the gradient of a multilinear function to $0$?
When you have a 1D function $f(x)$, the vector $x$ that satisfies $\nabla f(x) = 0$ is a stationary point which is a minimum when $f$ is convex.
Consider a multilinear function (linear in all ...
0
votes
1answer
31 views
constraint qualification for linear constraints [closed]
How to formulate conditions under which the LI CQ is fulfilled at arbitrary feasible point of the set of feasible solutions given by linear inequalities $S=(x\in\mathbb{R}^{n}:Ax\le b, x\ge 0)$? I ...
1
vote
0answers
44 views
Finding coloring with no subgraph isomorphism
This is a twist on standard subgraph isomorphism. Say I have two graphs $G(V,E)$ and $H(V',E')$ and the vertices in each graph are colored with one of $t$ colors. The subgraph isomorphism exists if ...
0
votes
0answers
31 views
Integer programming - “the carrier problem”
Motivation: The problem is to find the best solution of which of waiting packages should be packed first to a finite-space bus to deliver as many packages as possible at once.
Problem description: Let'...
4
votes
3answers
147 views
Extremal distribution of random variable that averages to a given value
Denote by $\mathcal M$ the set of probability measures over $[0,1]$ that average to $p$. This is a convex set and I am trying to characterize its extreme points. For any $x$, $y$ such that $0\leq x<...
0
votes
1answer
26 views
OLS/LAD on linear/quadratic programming type problem
I have a list of equations that define halfspaces (3 equation list example below)
$x_1 + x_2 + x_3 + x_5 < x_4 + x_6 + x_7 \\ x_4 + x_6 + x_7 < x_8 + x_9 + x_{21} + x_{43} + x_1 \\ x_4 + x_6 + ...
2
votes
1answer
28 views
asymmetric Dual of the asymmetric Dual is Primal?
It is known that in Linear Programming the Dual of the Dual is the Primal.
In wikipedia I saw that apart from the symmetric Dual I knew, there is also the asymmetric one:
https://en.wikipedia.org/wiki/...
0
votes
1answer
76 views
Given an LP problem how to transform the problem?
Given the following problem:
$$ \max. -3x_1 -2x_2 - \frac{9}{2}$$
$$ \text{s.t.} -x_1 + x_2 \le 0$$
$$ 5x_1 + 3x_2 \le 8$$
$$ x_1,x_2 \ge 0 $$
When we convert the LP into standard form and then ...
0
votes
0answers
23 views
optimalization problems
I do not understand in the optimization problems the following steps. Let us say we have the problem
$$\min(\text{or}\max) f(x)$$ subject to
$$p^{t}x=b$$
in some textbooks, I saw the Lagrange function ...
0
votes
2answers
52 views
Find the maximum value of the product of $x_1^1 x_2^2 \cdots x_n^n$ [closed]
Given $n$ positive real numbers $\{x_i\}_{i=1}^n$ satisfying $x_1 + x_2 + \cdots + x_n = n$, find the maximum value of $x_1^1 x_2^2 \cdots x_n^n$. That is,
$$\max_{x_1, \cdots, x_n} ~\prod_{i=1}^{n} ...
0
votes
0answers
21 views
Proper objective function implementation
This question is referred to from here.
I want to minimize the HD between $x_g$ and $x_h$ bit strings in the objective function in a Mixed Integer Linear Programming problem.
That is, Min $\sum_{l=1}^{...
0
votes
1answer
25 views
Linearizing constraint ( multiplication of binary variables)
I am trying to think of contraint(s) that can linearize constraint below.
$\sum_{T} \sum_{TR} Z_{(T,D)}* Y_{(TR,T)} \leq CAP_{(D)} \forall D$
Both Z nad Y are Binary Variables and CAP is capacity ...
1
vote
0answers
28 views
Converting a linear program to standard form when x is a matrix?
I have been using An Introduction to Optimization by Chong and Zȧk. In it there is a chapter about standard form and converting to it. This chapter makes sense to me. I think that I understand the ...
1
vote
0answers
47 views
minimize $(1/2)x^TPx+q^tx+r$ subject to $x^tx \le 1$
minimize $(1/2)x^TPx+q^tx+r$ subject to $x^tx \le 1$. The usage of the Lagrangian is not allowed.
I view it as a quadratic equation minimisation task. The way I see it I should take the gradient made ...
0
votes
1answer
25 views
Transportation Problem - Handling case of infinite capacity to supply
The problem is - In a standard transportation problem, with destination's demand limited, but each factory has unlimited supply to cater to the needs of destination. How should we modify the problem ...
1
vote
1answer
31 views
The basis for the null space of a linear transformation
I am given the following linear transformation
$$f: \begin{bmatrix}x\\
y\\
z
\end{bmatrix}\rightarrow\begin{bmatrix}x\\
x
\end{bmatrix}$$
and asked to select all answers which provide a basis for the ...
0
votes
1answer
38 views
How to solve this mathematical programming problem?
Suppose each point in the interval $[0,1]$ has some of a set of $N$ properties. The total length of the intervals with property $i$ is $x_i$ ($0\le x_i \le 1$).
Questions:
What is the maximum and ...
0
votes
1answer
26 views
If origin is not included in an LP problem how do we get a basic feasible solution?
Given the following constraints for an LP problem:
\begin{align}
x_1 + 2x_2 &\ge 4 \\
-3x_1 + 4x_2 &\ge 5 \\
2x_1 + x_2 &\le 6 \\
x_1 , x_2 &\ge 0
\end{align}
When I draw the feasible ...
0
votes
1answer
83 views
How to declare formulas for banded pricing model? [closed]
I am making an application (using JavaScript) where users should be able to create pricing models with a table. A user will have an ability to choose a table model. The table models are internally ...
1
vote
1answer
33 views
Build a cheaper highway
We consider a non-directed graph, where each vertex is a city and each edge is a possible road connecting two cities.
I need to build a cheap highway (a path on a graph) connecting all the cities ...
0
votes
0answers
5 views
How do I implement an aggregate probability constraint with uncertainty?
I am trying to model the following situation:
There are N customers and M shops. The demand of each customer is a normally distributed variable $d_{n}$ with mean $\mu_{n}$ and standard deviation $\...
0
votes
1answer
23 views
Square LP. Consider the LP with $A$ square and nonsingular. Minimize $c^Tx$.
Square LP. Consider the LP
$$\text{minimize }c^Tx\\
\text{subject to } Ax \le b$$
with $A$ square and nonsingular. Show that the optimal value is given by
$p^* = c^TA^{-1}b$ if $A^{-1}c \le 0$, and $p^...
0
votes
0answers
18 views
How to find the values of dual slack variables at the vertex $(w_{1}, w_{2})$?
Max $Z = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} $
Subject to
$Ax \leq b$
$x \geq 0$
If eliminate $x_{1}, s_{1}$ from Z, we get $Z = 45 - 2x_{2} + 3x_{3} - 4s_{2}$
What will be the values of the dual ...
0
votes
0answers
14 views
Doubt about notation in Robust Optimization
I'm studying the pricing model under Robust Programming here described from page 41 to page 45. I don't understand what's the meaning of subscripts $i$ and "second" $t$ referred to dual ...
0
votes
0answers
29 views
Linear programming of the Sinkhorn distance (entropy-regularized optimal transport)
\begin{align}
\mathcal{W}_\epsilon(\alpha, \beta) =& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\pi(x,y) + \epsilon H(\pi) \\
=& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\...
0
votes
1answer
47 views
Why is the distance matrix in optimal transport always the same, and doesn't actually measure distances between samples?
Why does the distance matrix computed in the optimal transport linear programming model always look the same (asides from its size changing with the number of histogram bins) no matter how the source ...
2
votes
0answers
35 views
minimal description of polyhedron
I have to find minimal description of a polyhedron $P$ described as follows:
\begin{align*}x_1 - x_2 &\leq 0\\-x_1 + x_2 &\leq 1\\2x_2 & \leq 5 \\ 4x_1 - x_2 &\leq 8 \\ x_1 + x_2 &...
0
votes
1answer
29 views
How to solve an optimization problems of this kind?
I have to solve a real-world optimization problem. I am teaching 33 students, a university lesson, and I am attempting to assign them 11 semester projects, based on their preference. I grouped them in ...
0
votes
1answer
63 views
Linear programming with a second decision variable in the constraint vector
Is the following optimization problem feasible (modified optimal transport)? The primary decision variable appears in the objective function as $\mathbf{x}$, whereas the second decision variable $\...
0
votes
0answers
18 views
Fixed Strike Lookback Call Option with Linear Programming - Question about notation
I am aware, given the number of unanswered questions, that the probability that somebody answer is almost zero, but I'll take my chances. I am trying to understand how to evaluate fixed lookback ...
0
votes
1answer
28 views
How to derive the dual for LP like this?
I know how to derive dual for normal LPs, but what if we are unlikely to have something like this:
maximize z
s.t. z < 3y-2
1 < y < 2
, where the ...
0
votes
1answer
32 views
Filling a piecewise continuous linear shape with a constant volume of liquid
We have a piecewise continuous linear function (representing topography). The shape is to be filled with a constant volume of liquid (representing an ocean). How can we find the 'sea level', and where ...
0
votes
1answer
16 views
Converting set of inequalities to LP
I have a problem where I have a bunch of inequalities in the form:
$a_{1,1}b_{1,1} + a_{1,2}b_{1,2} + ... + a_{1,n}b_{1,n} >
a_{2,1}b_{2,1} + a_{2,2}b_{2,2} + ... + a_{2,n}b_{2,n}$
$a_{2,1}b_{...
0
votes
0answers
22 views
Where did we use Ax=c to prove local min is global min
Prove that a local min is also a global min
I understood all the steps in this problem and I was able to prove a, b and c in the hint. But I don't understand where did we use the fact that Ax=c. I ...
2
votes
0answers
32 views
Can this dual LP be solved?
The primal problem is as follows:
$\min w=2x+4y+5z+3q$
subject to
$$
\begin{split}
-x - 2y + 2z &\geq 40\\
-3x - 2z - q &\geq -100\\
x - 2y - z + 4q &\geq 50
\end{split}
$$
I have ...
0
votes
0answers
39 views
Why is it that a 3x3 math puzzle can have no more than 5 unknowns?
I'm going through the Brillient.org Algebra 1 course, and I came across a problem that I don't think was well explained, and I'm hoping I can find more insight here.
So this type of problem, for some ...
2
votes
0answers
97 views
Pools of problems
Using a pool of problems, 16 tests will be formed.
Every test should have the same number of problems.
Any problem should be included in at most 8 tests.
For every 4 tests, there should be at least 1 ...
0
votes
2answers
34 views
Assigning tasks to minimize cost
I have a set of jobs that must be done on a given day in sequence. $J_1, J_2, J_3$, with deadlines $D_1, D_2, D_3$. There are three workers $W_1, W_2, W_3$ that can execute the tasks each one with ...
2
votes
0answers
118 views
The transportation problem with uncertain (and, in general, linearly interdependent) supply- and demand values
I'm looking at a transportation problem:
$$\min_{x_{ij}} \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$$
subject to
$$\sum_{j=1}^nx_{ij} = s_i, \mbox{ for all } i=1,...,m.$$
and
$$\sum_{i=1}^mx_{ij} = d_j,...
0
votes
0answers
28 views
Transbordo Localización
If someone could help I will thank him or her a lot, its a problem of linear programming, im taking a course in Spanish, but I don't understand it , they are using Excel solver and want me to use ...
-1
votes
1answer
17 views
What is the upper bound for edges that are not going in or out of node 1 in this graph?
I have the following graph with the following problem:
We want to obtain a Hamiltonian cycle by supplying all nodes with 1 unit of flow. Initially the node 1 will send 4 units of flow through one and ...
0
votes
1answer
18 views
Is it possible to know if the feasible region is unbounded without drawing it?
Given the following set:
$$ -x_1 + x_2 = 4$$
$$ x_1 - 2x_2 + x_3 <= 6 $$
$$ x_3 >= 1 $$
$$ x_1,x_2,x_3 >= 0 $$
Without drawing the feasible region can I know if it is bounded or unbounded?
0
votes
1answer
36 views
How do you enter a variable>variable inequality constraint into a Simplex method calculator?
In 2-variable linear programming problems, constraints can take the form of either $aX+bY < C$ or $mX > nY$. Both lines graph to form linear bounds so the graphical solution applies. But in 3+ ...
0
votes
0answers
29 views
solve the linear problem with graphic method.
\begin{equation}
2x_1 + 3x_2 \geq 6
\\-5x_1 + 9x_2 \leq 12
\\ 2x_1 - 3x_2 \leq 6
\\ x_1 + x_2 \leq 5
\\ 0 \leq x_1 \leq 4
\\ 0 \leq 2x_2 \leq 5
\\ \min z = -3x_1 - 2x_2
\end{equation}
solve the ...
