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.

0
votes
1answer
23 views

Using the primal solution solve the dual sloution

For: $$\text{Max } z=2x_1+2x_2$$ $$\text{ s.t } 2x_1+x_2\leq 16$$ $$3x_1+2x_2\leq 25$$ $$2x_1+3x_2\leq 25$$ $$x_1+x_2\leq 16$$ $$x_1,x_2\geq 0$$ Solve the primal, and solve ...
1
vote
0answers
43 views

Differential of partial minimization

Let $\mu_1 \in \mathbb{R}^n $ and $\mu_2 \in \mathbb{R}$, $h(\mu_1, \mu_2)$ be a concave function in $\mu_1, \mu_2$, and let \begin{equation} G(\mu_2) = \underset{\mu_1 \geq 0}{max} \,\, h(\mu_1, \...
3
votes
0answers
27 views

Reducing the Eulerian cycle problem in a mixed graph to a maximum flow problem

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is ...
1
vote
1answer
27 views

Reformulate an optimization problem with absolute values as a linear program

Reformulate the following optimization problem as a linear program. $$\begin{array}{ll} \text{minimize} & 2 x_1 + 3 |x_2-10|\\ \text{subject to} & |x_1+2|+|x_2|\leq 5\end{array}$$ First, ...
1
vote
1answer
34 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
30 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
26 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
46 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
45 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
42 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
23 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
27 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
26 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
74 views

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
29 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 ...
1
vote
1answer
34 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
88 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
10 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
130 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 ...
1
vote
1answer
23 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
25 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
27 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
31 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
28 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 ...
0
votes
0answers
28 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
50 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
33 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
47 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
28 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
30 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
25 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
30 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
58 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
42 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
73 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
24 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
22 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
29 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
22 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
31 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
24 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
38 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
52 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
39 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 ...