Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
47 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 ...
0
votes
1answer
51 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 ...
2
votes
0answers
50 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 ...
0
votes
0answers
27 views

Split classroom sizes in half linear integer programming

I work for a school who is looking to split students into two groups for COVID related reasons. Ultimately we need to split the students by class section and try to keep families to be in the same ...
6
votes
1answer
198 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 ...
0
votes
0answers
41 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
1answer
108 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
1answer
146 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?
2
votes
2answers
108 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 ...
0
votes
0answers
42 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
0answers
69 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 ...
0
votes
0answers
73 views

Are there unproblematic max constraints when modelling problems as Linear Programs?

Suppose we have a linear objective function that we want to maximize. All variables are from the set of reals. We have a constraint of the form: $$\max(x_1,x_2) + \max(x_3,x_4)\leq c\,, \text{ with } ...
2
votes
0answers
57 views

Interior point of convex polytope

Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
-1
votes
1answer
39 views

FORM by NIKHEF: unexpected behavior wrt summation

I have two almost identical FORM (by NIKHEF) scripts here: script_1 script_2 which differ only in summation at the end. In first case the summation in done in one step, in the second case ...
3
votes
0answers
52 views

Hit-n-Run Monte Carlo on convex polytope

So, I'm currently trying to implement a MCMC to uniformly sampling hyper-points from the polytope defined as $\mathbb{K}=\{x\in\mathbb{R}^{n}\;\;\text{s.t.}\;\; A\,x=b \}$ in the specific case where, ...
1
vote
0answers
17 views

Long AMPL model preparation time

We deal with a large-scale linear optimization problem (~50000 variables and ~4000000 constraints). We use AMPL Studio modeling environment for problem modeling and then calling linear solver (CPLEX, ...
2
votes
1answer
101 views

Getting Extremal Rays of Cone

So I have a set of linear homogeneous equations $A\vec{x}=0$. I would like to solve this for non-negative solutions. I can solve the system in general and I get the two vectors that span the solution ...
2
votes
1answer
85 views

Is it more efficient to capture many constraints in one constraint?

I have a number of variables that need to be set to 0. They are positive real numbers so the way I see it I can do this by setting each one to 0 by separate constraints, or I can set their sum to zero....
1
vote
1answer
80 views

Is there a name for this integer linear optimization problem?

I have an integer linear programming problem of the form: $$\DeclareMathOperator{\tr}{tr} \min \tr WX$$ subject to: $$\begin{align} \sum_j X_{ij} < c_i && \forall i \\ \sum_i X_{ij} = 1 &...
4
votes
1answer
54 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
2
votes
3answers
518 views

Find a solution of large system of inequalities

I have a large system of homogenous inequalities involving 33 real unknowns of the form $$ \vec{F}(z_i)^T \cdot \vec{X}>0\, $$ where $\vec{X} = \left(x_1,...,x_{24}\right)^T$ are the unknowns and ...
5
votes
1answer
98 views

What is the name for this type of constraint?

I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take ...
3
votes
0answers
92 views

Solving multiple linear programs with same constraints but different objective

I have ~30 non-negative variables and 24 equations and I want to find out the upper and lower bound for each variable. Feasible solutions are guaranteed. So for each variable, I solve two LP problem, ...
2
votes
0answers
42 views

Where can I find sample data for large linear programming optimization problems?

I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
1answer
156 views

Splittable and non-splittable flows in the network flow problem

I am working on a multi-commodity flow problem where for a graph $G=(V, E)$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as ...
3
votes
1answer
89 views

What is a "good enough" method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?

Given triples of $n$ floating point values $$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$ and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that ...
2
votes
0answers
62 views

Weighted Set Cover in practice, beyond the greedy algorithm

According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ...
2
votes
0answers
53 views

Transforming an arbitrary linear program into one with an interior point

Primal-dual interior point methods for linear programming require interior primal and dual starting points. I am looking for a good reference containing a description for modifying a given linear ...
7
votes
1answer
1k views

Ways to speed up solving an LP with Google's ortools

I'm having an issue solving an LP of the form: $$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$ The specific problems I'm running into ...
2
votes
0answers
268 views

Finding integer/lattice points (coordinates) inside a polytope/polyhedra?

I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that ...
1
vote
2answers
69 views

implied equalities and relative interior

What is the best method to find for a linear system of inequalities $Ax\ge b$ with dense $A$ of moderate dimension the affine subspace spanned by the feasible points (i.e., the implied equalities $(Ax)...
3
votes
1answer
374 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
1answer
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: \...
0
votes
1answer
821 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 ...
3
votes
1answer
61 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
3answers
133 views

Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?

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
1answer
156 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 ...
3
votes
3answers
2k views

Checking the feasibility of a system of inequalities

I have $m$ inequalities involving $n$ variables as follows $$a_{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
0answers
111 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
0answers
75 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
1answer
118 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
0answers
232 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{...
1
vote
0answers
47 views

Help formulating/finding the general class of this problem

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_{...
4
votes
0answers
671 views

Precision of ratio constraint in a linear program [closed]

I am trying to solve a LP in which one of my constraints is of the form $$\frac{A(x)}{B(x)} = 1$$ I transform this constraint into a linear one $$A(x) - B(x) = 0$$ However when CPLEX solves the ...
1
vote
1answer
126 views

Literature on comparing Simplex and Interior-Point-Methods (or combining both of them)

Do you know some interesting literature concerning the comparison of Simplex and Interior-Point-Methods referring to linear optimization? I also read about the possibility of combining both of them ...
2
votes
1answer
170 views

linear programming feasiblity checking

Is there any sufficient and necessary condition to check the feasibility of the linear constraints $Ax=b, x\geq 0$ without solving an LP with a constant objective function? $x$ is the variable and $...
2
votes
1answer
79 views

From deterministic to stochastic LP formulations

I am having a hard time understanding the very first example in "A Tutorial on Stochastic Programming". More specifically the authors show that one can formulate the stochastic variant of (1.2) ...
1
vote
0answers
52 views

I'm using linear programming for production planning. Does the order in which I make products affect the cost?

I have a collection of different scrap aluminium alloys. I want to mix them together to make new alloys with customer-defined compositions. Sometimes this will involve little more than melting down ...
0
votes
1answer
61 views

Maximize Result For 4 variable

A factory has $A$ and $B$ products. $A$ is made with $4X + 2Y$ raw materials. $B$ is made $2X + 4Y$ raw materials. We want to maximize total profit. Input amount of profit $A$ per item, amount of ...
1
vote
2answers
367 views

How to solve a constrained optimization problem using minFunc or minConf

I am trying to solve the following optimization problem: \begin{align} &\min\limits_{s} \rm{tr}\left(S^T S\right) + \mathrm{tr}\left(\left(S^T S\right)^{-2}\right)\\ &\text{subject to }\rm\...