# Questions tagged [linear-programming]

Referring to optimization problems that consist only of linear constraints and a linear objective function.

137 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

### Constraints involving max in ILP

Consider $n$ apps and $m$ transactions. $x_{ij}$ is a binary variable, it takes 0 or 1. $x_{ij}$ takes 1 if $i$th app is used for $j$th transaction, else 0. min $\sum_{i=1}^{n}\sum_{j=1}^{m} x_{ij}$ ...
49 views

### Linear Programming with bounds on magnitude

I have a set of halfplanes $H$, and a target vector $T$. My goal is to find the vector $v$ closest (2-norm) to vector $T$, such that $v$ is in the intersection of all of the halfplanes. This can be ...
51 views

### When is it worth it to use the dual simplex method with warm starts?

Let's say I have a linear program that incurs a series of slight changes to it, so I want to warm-start it. I've read various things that recommend using the dual simplex algorithm over the primal ...
1 vote
60 views

### Package Assignment problem to maximize profit

Problem description We have a graph $G=(V,E)$. $V$ is the set of nodes. $c_{ij}$ is the profit of traveling through edge $(i,j)$. $T=\{1,2,3,...\}$ is the set of discrete time steps. At each time step,...
1 vote
91 views

### Using absolute error as the cost function

This is related to my previous post Minimize distance between curves. I have a dataset with values of multiple curves. An example plot is shown below. I want to scale the curves (move up/down) so that ...
89 views

### How can we model time progress in linear programming?

I am trying to solve a scheduling problem with linear programming. I have N disks that each have a capacity of constant C. At each time interval t_i, a set of write requests with different sizes ...
99 views

### Linearize problem with absolute value

Is there any method to linearize the following optimization problem? \begin{align} min_{x,y} &~~ c~[x; y] \\ st &~~ \sum x\leq \alpha_1 \\ &~~ \sum |y|\leq \alpha_2 \\ &~~ \sum y= 0 \\ ...
1k views

### Python solvers for MINLP in Pyomo in Google Colab

I am looking for a MINLP solver that works with Pyomo models which can be used in the Google Colab environment. I have already found MindtPy but it doesn't work in google colab.
64 views

### Equivalence between zero sum games and linear program

It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the ...
137 views

### Maximum Constraints Satisfaction of Linear Programming

The question I need to solve is to maximize the satisfied constraints in linear programming. To be more specific, Suppose I have an infeasible LP problem, my goal now, is to find the maximum number of ...
106 views

### Model and solve nutrition optimization problem: how to?

How to solve/assess the following problem? Given: $N$ ingredients like apples, bread etc. Mass of an ingredient $j$ is in this simplified model a sum of macro nutrients carbohydrates, proteins and ...
216 views

### Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$

I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
75 views

### Balanced constraint

In several optimization problems, we found what we called the balanced constraint(c^T • x = z ) For exp: C^T • 1 = 0 (C is a binary Matrix) Can I have an intuitive explanation about the concept and ...
1 vote
231 views

### Linear system with an l1-norm constraint

I have a saddle-point system of the form \begin{equation} \begin{bmatrix} A & B \\ B^T & O \end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} f \\ \vec{0} \end{bmatrix}, \end{...
1 vote
457 views

### Solving a linear program with an active set method

Is it possible to solve a linear program with an active set method? If so what would be the similarities and differences to the simplex method?
122 views

### Using MILP to place a set of primers along a genome

Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$. Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located). Let ...
46 views

### Optimizing vectors with equal elements

I am trying to distribute power across different devices, so that the sum is as equal as possible to the power setpoint. At the same time, the sum of power per phase must not exceed the power of the ...
1 vote
105 views

### Fastest way to solve linear programming with 6 complex inequalities and 5 nonnegative variables

I have a program where I need to solve a linear programming problem in a fast loop. The language I'm using is Java and any kind of bindings to other languages are not acceptable. Libraries might be ...
92 views

62 views

501 views

### Why do active set methods or the simplex method pivot only one variable at a time?

Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
1 vote
2k views

### Solve a set of multivariate linear inequalities with constraints in Python

I'm trying to implement Dinur-Nissim algorithm and am stuck at how to solve the set of linear inequalities with multiple unknowns and a large number of equations along with constraints. Example: \...
866 views

### How to perform linear programming sensitivity analysis in MATLAB?

I would like to perform post-optimal analysis using Matlab linprog. But it does not provide any information about that. So required a way to get the info about optimal basis, basic and non-basic ...
67 views

### Linear programming with stochasticity?

Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution. Now, I would like to solve the same problem but with stochasticity ...
1 vote
I have an optimization problem that I'm trying to cast as a linear program. However, I have an objective function of the form \begin{array}{ll} \text{maximize} & a_1 x_1 - a_2 \lvert x_1\rvert\\... 5 votes 1 answer 192 views ### Largest hypercuboid inside a polyhedron Given a polyhedron \mathbf{Ax} \leq \mathbf{b}, how to find the largest hypercuboid, with unknown center \mathbf{x_{0}} and side lengths 2\epsilon_{i}, which are aligned along the co-ordinate ... 4 votes 3 answers 3k views ### Checking the feasibility of a system of inequalities I have m inequalities involving n variables as followsa_{1,j} x_1 +a_{2,j} x_2 +\dots +a_{n,j} x_n>0 \quad \text{for} \quad 1 \leq j \leq m$$How can I check if a solution exists (with the ... 1 vote 0 answers 147 views ### Generate discrete set of points in a feasible region I have two vectors which specify the bounds x_{min} and x_{max} of the sample space. Also, it has to satisfy the linear constraint Ax \leq b. How to generate an evenly spaced set of points, ... 3 votes 0 answers 81 views ### linear relaxation of an optimization problem I'm reading an article lately, and there is one point which confuses me. So, we have the following constrained binary quadratic problem. min x^{T}Qx with the constraints that Ax≤b and x\in {0,... 0 votes 1 answer 170 views ### Perturbation in bounds given the perturbation to constraints Given a feasibility problem with both inequality and equality constraints, I'm interested in the sensitivity of the bounds of the region to changes in the constraints. To help with answering the ... 1 vote 0 answers 251 views ### Variable elimination in linear programming I have a linear program of the form$$\underset{P,\;g}{\text{Minimize}}\hspace{3mm}c^Tg \begin{align} \hspace{17mm}\text{Subject to}\hspace{3mm}AP_{\cdot,j}&=\begin{bmatrix} -g\\ d \end{...
Imagine a bus serving a line with N stations. Each station, $i, i=1,…N$, has $s_{ij}$ passengers that want to board the bus to go to $j$, $\forall j \neq i$. (one direction). So there are \$\sum_j s_{...