Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

3
votes
2answers
84 views

How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

So, there's this problem: maximize $$6x_1 + 8x_2 + 5x_3 + 9x_4$$ subject to $$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\; x_1, x_2, x_3, x_4\geq0$$ The solution is obvious: since the sum of ...
0
votes
1answer
42 views

Finding restrictions and convex hull by having a set of extreme points

Suppose we are given a set of extreme points. Is it possible to find out all possible restrictions of the Linear Programming problem by having those extreme points? Well, if we have a linear ...
0
votes
0answers
81 views

Proof verification for simplex method problems

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem: Consider the simplex method applied to a standard form ...
0
votes
2answers
37 views

After Farkas Lemma, transforming $(A, -A)x = b$ into $Ax=b$

Let $A \in \mathbb R^{m\times n}$ and $c \in \mathbb R^{m}$ Show that either (i) $Ax=c$ has a solution or (ii) $c^{T}y=1$ with $A^{T}y = 0$ has a solution. My proof: Let (ii) be satisfied iff ...
1
vote
1answer
37 views

Solving linear Programming problem with simplex method.

I have tried this question but can't come up with a maximization answer. I am not certain where I am wrong but I think my equations have an issue, you can't take look at them below the question. The ...
0
votes
1answer
54 views

Solving weighted least squares with non-negative constraints

I have the optimization problem $$ \begin{align} \min_{\mathbf{P} \geq 0} \|\mathbf{A\odot(X-PQ^\top)}\|^2 + \frac{\|\mathbf{P}\|^2}{2} \end{align} $$ $\odot$ is the Hadamard product, $\mathbf{A,X,P,...
0
votes
1answer
13 views

Proving infeasibility using Duality

suppose we have the linear program min{$c^Tx: Ax \leq 0, x \leq 0$} and its corresponding dual max{$0^Tx: A^Ty \geq 0, y \leq 0$}. How can we show that the Dual is infeasible? I started by ...
1
vote
1answer
35 views

Modeling $t \in [a,b] \; \Rightarrow y_{[a,b] }=1$, asking for alternatives if any

Suppose you have a variable $t\ge 0 $, I want to model the following statement : $$ t \in [a_i,b_i] \; \Rightarrow y_i =1 $$ I am assuming $t$ belongs to a unique interval among the ones proposed. I ...
1
vote
1answer
30 views

Set of optimal directions is a cone

Let $\vec{u}$ be an optimal point for the linear programming problem: \begin{equation} \min{ \vec{c}^T \vec{x}}\\ \text{s.t. } A\vec{x}=\vec{b} \text{ and } \vec{x} \geq \vec{0} \end{equation} where $...
1
vote
1answer
28 views

Dual of conic program

Let $A$ be an $m \times n$ matrix (over $\mathbb{R}$), $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$ and $K \subseteq \mathbb{R}^n $ is a closed, convex, pointed cone with non-empty interior. We define a ...
1
vote
1answer
46 views

Strong Duality: If Dual is optimal then primal is optimal

Strong duality states that if the Primal has an optimal solution then the Dual has an optimal solution. Is the converse of this statement true? To me it would seem intuitive that it is, but I just ...
0
votes
0answers
42 views

Can row/column penalty be zero in Vogel's Approximation Method?

If I have row with the following digits 10, 5, 12, 16, 5, 7 Will the row penalty be 5-5=0 or 7-5=2 In most books they ...
1
vote
1answer
50 views

Correctness of integer reformulation in the FICO MIP quick reference

I have stumbled upon an industry quick reference for MIP formulation by FICO: However, after checking their writing on section 2.3 Maximum value. It seem that there are problems with their ...
0
votes
1answer
30 views

What exactly is a basis matrix in LPP?

I'm studying simplex for solving a LPP. $A$ is a $m\times n$ matix. $$Ax=b$$Then the book says: Let $x$ be a basic feasible solution to the standard form problem. Let $$B(1), B(2),\cdots B(m)$$ ...
0
votes
0answers
33 views

How can this linear problem be infeasible?

I have the following linear problem which is primal: I have converted this problem to its dual and tried to solve using the lpSolveAPI in R programming language. However, the ...
1
vote
1answer
38 views

Iterative algorithm for a simple linear optimization problem

Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^...
0
votes
0answers
59 views

Optimize the product of three binary variables: convex relaxation and integer solutions

I am working on a problem related to graphs and I formulated the problem as follows: $$\max_{y,e} \sum_{i=1}^n (c_i^1 y_i^1 + c_i^2 y_i^2) + \sum_{(i,j)\in E}(d^1y_i^1y_j^1e_{ij} +d^2y_i^2y_j^2e_{ij})...
0
votes
0answers
46 views

How to linearize the following constraint of product of binary and continuous variable

How can I linearize a constraint that contains the product of a continuous variable and a binary variable? Is it possible to linearize it? Thank you very much.
1
vote
0answers
30 views

LP where I need to take medians of multiple sets of variables

I have an LP optimization problem where I need to impose a linear constraint on the result of a median filter applied to an image. The issue is that the image already has had possible transformation ...
0
votes
1answer
30 views

Can the simplex method be used for general monotonically increasing objective functions?

The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's ...
0
votes
1answer
39 views

Simple quadratic inequality

Show that $${\bf x^T V x}\leq \left( \sum_{i=1}^n v_{ii}x_i \right)^2$$ knowing that $\bf V$ is symmetric and positive semidefinite. It should be simple, but can't figure it out. Thanks!
0
votes
0answers
16 views

Name to specific fit

I have been looking for the name of a specific fit. I was in need of a function that minimized the error (L1) between the function and the observed values but the function must be greater than or ...
2
votes
1answer
37 views

How many kilograms of each type of fertilizer should the farmer use?

A farmer has a supply of chemical fertilizer of type A which contains 10% nitrogen and 5% phosphoric acid, and type B which contains 6% nitrogen and 10% phosphoric acid. After testing the soil ...
0
votes
0answers
32 views

Convert Problem to a Linear Programming (Piecewise Functions)

I want to write the following problem as a linear program: $$minimize_x \sum_{i=0}^m{h_w(a_i^Tx-b_i)}$$ $$ h_w(u) = \left\{ \begin{array}{ll} |x| & \quad |u| \leq w \\ ...
0
votes
0answers
28 views

Solving a constrained linear system of equations

I want to solve the linear system of equations $$ \begin{equation} Ax = b \\ \text{s.t} \quad x \geq 0 \end{equation} $$ The matrix A is a sparse symmetric matrix. What is the best time efficient ...
0
votes
0answers
21 views

In linear programming, what does the primal problem imply about the sign of the dual variables?

In Bertsimas' Introduction to Linear Optimization, we define the primal problem in standard form as minimizing $c'x$ subject to $Ax=b$ and $x\geq0$, and the dual problem as maximizing $p'b$ subject to ...
0
votes
1answer
37 views

How would Jack allocate his time to maximize his pleasure?

Jack is an aspiring freshmen at a university. He realizes that “all work and no play make Jack a dull boy.” As a result, Jack wants to apportion his available time of about $10$ hours a day between ...
3
votes
0answers
43 views

How to quickly determine if a linear program is feasible?

I have a series of linear programs in canonical form $$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ and I need to ...
2
votes
1answer
70 views

Open Travelling Salesman Problem

I am trying to find a linear program for the open Travelling Salesman Problem, where the salesman does not need to return to the starting point. More precisely, I have to do this with multiple ...
1
vote
0answers
20 views

Inner and outer linearization

Why are Dantzig-Wolfe and Benders decomposition referred to as inner and outer linearization respectively? I am a newbie in Mathematical Programming and optimization and came across these terms while ...
0
votes
1answer
32 views

Check that $x$ can be taken to be an extremal point of $A$

Let $T : \Bbb R^n \to \Bbb R$ be a linear map. Let $A \subset \Bbb R^n$ be a convex, closed and bounded set. We know that there exists $x_0 \in A$ such that $\sup T(x) = T(x_0)$. Check that $\...
2
votes
0answers
79 views

Could I have two optimal solutions - linear programming problem?

A company produces two different products. They require two types of ingredients: M and N. The first product require 90 grams of the ingredient M and 10 grams of the ingredient N. The second product ...
0
votes
0answers
28 views

Tools for generating constraints for linear programs

Are there any freely available tools that aid in generating LP formulations in a way that can be fed into some solver? Say I have a few hundred variables, all which have to satisfy the same ...
0
votes
0answers
23 views

mixed integer linear programming problem

Consider following mixed integer linear programming problem: finding a parking plan for set of cars K={1,...,k} with various lengths. parking is organized in lines P={1,...,p}, legth of a parking ...
1
vote
0answers
53 views

how to set up an optimization problem to split a group of people into two groups, with several constraints

I am a bit stuck with this problem; I found a temporary (an perhaps suboptimal) solution using Excel, but I'd like to hear your opinion /advice, please. 9 people want to form a group and go on on a ...
0
votes
1answer
67 views

Simplex algorithm/basic artificial variable

How do we continue in the simplex algorithm if some artificial variable is basic ? Do we still forget about this basic artificial variable in the second phase of the simplex algorithm as we do forget ...
1
vote
0answers
33 views

Finding the equilibrium conditions for the Chebyshev approximation problem

$$-x_0 ≤ \sum_{j=1}^n a_{ij}x_j-b_i ≤ x_0 $$ $$ i=1,...m$$ $$\mathrm {min} x_0 $$ (Forgive me if I made any formatting mistakes; I'm not familiar with MathJax) I know better than to try and use ...
0
votes
1answer
45 views

linear programming set a variable the max of another

I'm new to programming and writing models. Most of the models I studied have straightforward objective functions and easy constraints that simple inequalities. I'm trying to write a constraint that ...
0
votes
0answers
67 views

How To Use The Simplex Method When Having More Variables Than Constraints

I have been learning the Simplex Method for solving minimization and maximization problems, but came across a small problem with every resource I have found online. They all seem to imply that ...
0
votes
0answers
32 views

Non-Linear to Linear with Auxiliary Binary Variables

The Problem: Formulate the constraint $u = \min\,\{x_1, x_2\}$ with linear constraints and binary variables. We assume that $0 \leq x_i \leq 10$ for $i = 1, 2$. Specify the value of every big-M ...
2
votes
1answer
47 views

Is any $k$-th largest element of $\{\mathbf{w}_1^T\mathbf{x},\cdots,\mathbf{w}_n^T\mathbf{x}\}$ piecewise linear?

Problem This question is motivated by this answer, which represents $k$-th largest element of a set $\{a_1,a_2,\cdots,a_n\}$ (elegantly) as $$ \min _ { I \subseteq [ n ] \atop \vert I\vert = n - k + ...
1
vote
1answer
50 views

Why is it that we can ignore non-basic variables using the simplex method of linear programming?

I'm studying the simplex method of linear programming. When a result is reached, the slack variables usually are non-basic and the variables of interest are usually basic, but I recognize that this ...
0
votes
1answer
28 views

How to find an extreme feasible point in a linear polytope (set $\{x : Ax \leq b\}$ defined by halfspaces)?

The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $H$-polytope) and is defined as the intersection of a finite number of halfspaces. The simplex method for the ...
2
votes
1answer
48 views

Taking Dual of a Linear Program

Take the dual of the following LP: min $x_1 + x_2 + 4$ such that $$\begin{bmatrix} 1 & 3 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\x_2 \end{bmatrix} \leq \begin{bmatrix} 10 \\ 21 \end{...
1
vote
0answers
40 views

On linear systems of inequalities: stability and continuous dependence

Let $A$ be a $m\times n$ matrix and $b\in\mathbb{R}^m$ a vector, which define the set $$ S(A,b):=\{x\in\mathbb{R}^n\::\:Ax\leq b\}. $$ Let $A_k\to A$ and $b_k\to b$, w.r.t. some norm, such that all ...
0
votes
1answer
42 views

Linear programming instance/Online solver

Does anyone know what in this online linear programming problems solver AFTER clicking on the green button SOLVE is the meaning of the numbers below $t$, i.e. in the last column: $\frac{1}{9},\frac{1}{...
1
vote
1answer
49 views

Correct terminology for optimization problem

An optimization problem aims to minimize the sum of a variable u over a time-series. It is made of three variables that are in a linear relationship. Two binary variables $$x_1, x_2, \dots x_n$$ and ...
2
votes
0answers
42 views

First step of simplex algorithm

I have the following linear program: Maximize $15x + 2y + z$ subject to $$x \le 10 \\ x + y \le 17 \\ 2x + 3 \le 25 \\ y + z \ge 11$$ I created the following Simplex Tableau: ...
0
votes
0answers
34 views

Linear programming in detail

I would like to know why here on the page 30, the author writes about absolute values, at all ? Phase I: minimize the sum of the artificial variables, starting from the BFS wherethe absolute value ...
1
vote
1answer
178 views

Linear programming: how to determine if the basic solution is feasible or infeasible?

I have the primal and dual problem (with slack/excess variables) Primal min $x_{1}+3x_{2}$ s.b. $x_{1}+w_{1}=3$ $x_{2}-w_{2}=2$ $x_{1}+2x_{2}-w_{3}=6$ $x_{1},x_{2},w_{1},w_{2},w_{3} \geq 0$ ...