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.

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 &...