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
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^{+...