Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

3
votes
1answer
53 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 ...
1
vote
0answers
19 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
46 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 ...
4
votes
1answer
106 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 ...
1
vote
0answers
69 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
51 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
118 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 ...
0
votes
0answers
103 views

How to efficiently solve badly scaled linear equation system (regression)?

For a project I have to estimate parameters of a function in least-square sense. Up to now I did this with Matlab and lsqnonlin() what worked quite well. Now I have to use this regression-algorithm in ...
1
vote
1answer
489 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
353 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
48 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
99 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
114 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 ...
2
votes
3answers
262 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
71 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, ...
4
votes
0answers
71 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
60 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
122 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
43 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_{...
5
votes
0answers
340 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
46 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 ...
3
votes
1answer
79 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 $...
3
votes
1answer
49 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
32 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
44 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
259 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\...
1
vote
0answers
43 views

Admissible box constraint for a quadratically constrained linear program

I am looking at a real-world resource allocation problem that is cast as a quadratically-constrained linear program of the form $$ \max\langle f,x\rangle $$ subject to $$ \begin{aligned} m \leq\,\, &...
4
votes
0answers
81 views

ADMM for Linear Program over graph

I want to use ADMM to solve a LP defined over a graph. According to Distributed optimization and statistical learning via the alternating direction method of multipliers S. Boyd, N. Parikh, E. ...
1
vote
1answer
77 views

Simplex method - cycling and condition “>=” or “>” in choice of pivot row

I'm coding the simplex method and observing that it easily falls into cycling, even if Bland's rule is used. It seems to me I have found the reason and I would like to check my understanding is ...
6
votes
1answer
259 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
3
votes
1answer
315 views

Is the “practical” complexity of linsolve direct solver O(n^2) ?

I recently timed the linsolve direct solver and I was kind of shocked to see that the solver seemed to be scaling quadratically even upto a 1000 dimensions. Specifically I ran the following code and ...
5
votes
1answer
738 views

Implementation of LP with separation oracle?

I'm looking for an implementation of the ellipsoid algorithm for linear programming since the application I have in mind has the constraints represented as a separation oracle. Is such an ...
2
votes
1answer
44 views

linear objectives and constraint except for S^2+C^2=1

I have an optimization problem with linear objective, and constraints that are all linear except for one constraint of the form $S^2+C^2=1$, which corresponds to elements in a rotation matrix. What ...
1
vote
0answers
40 views

Probabilistic model to approach problem that is usually dealt with linear programming

I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
1
vote
2answers
150 views

Breaking symmetries in a (binary) integer program

I want to solve a integer programming problem with binary variables $x_1,\ldots,x_n.$ I have a permutation group $G \leq S_n$ such that for every $f \in G$ the vector $\overline{x}_1,\ldots,\...
0
votes
1answer
58 views

Convert the following model into an LP model (not asking for standard form), includes a max (a,b,c,d)

Convert the following model into an LP model. Note that you're not being asked to convert this to standard form. $$\min z = \max (x_1, x_2, x_3, 2000)$$ s.t. $$-2x_1 + x_2 + x_3 \geq -4$$ $$3x_1 - ...
7
votes
1answer
370 views

Linear system solution with inequality constraints - methods?

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this? Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{...
0
votes
1answer
74 views

Can Variance be replaced by absolute value in this optimization problem

Initially I modeled my objective function as $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$, $x$ are linear functions. To be able to solve ...
3
votes
1answer
70 views

Use scipy to get any vertex of polytope

I need to get just a random vertex of a polytope. Any will do. The only way I can do this now is to pick a random function (say 0s) to maximize with scipy.optimize.linprog. However, this is wasteful, ...
1
vote
0answers
57 views

Solving an LP greedily

I have the following LP: $$ \begin{array}{ll} \text{Minimize} & \sum_{j=1}^n x_j \\ \text{Subject to} & \sum_{j=1}^n a_{ij} x_j \geq b_i,~~~i\in\{1,\ldots,M\} \\ & 0 \leq ...
4
votes
1answer
71 views

LP and SDP nomenclature

A canonical form of primal linear program is $$ \text{minimize } c^T \cdot x \\ \text{subject to } Ax = b, x \geq 0 $$ The dual is $$ \text{maximize } b^T \cdot y \\ \text{subject to }...
1
vote
1answer
161 views

Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
2
votes
0answers
89 views

Resources for large-scale MILP optimization

With the advent of "big data" applications, different algorithms have to be used to efficiently solve optimization problems, even in the convex case (e.g. the recent success of stochastic gradient ...
0
votes
2answers
461 views

GAMS solvers: which one to use

The other day I had a discussion with a friend about the GAMS solvers and we were wondering what are the mathematical differences between the solvers. Which one to use for which kind of problem? How ...
1
vote
1answer
202 views

Solving nested MILP problems

I want to solve a family of MILP problems (indexed by $k \geq 0$) of the following type: $$ \begin{align} \max \; c^Tx \;\; s.t. \\ Ax \leq b \\ d^Tx \leq k \end{align} $$ In other words, the ...
1
vote
0answers
94 views

Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
0
votes
1answer
107 views

MAX-SAT and MAX-cut

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
0
votes
2answers
232 views

MILP formulation and optimization

For $i=1, \dotsc, K$, we have $n_i$ ordered real numbers: $$ x_i(1) \leq x_i(2) \leq \dotsc \leq x_i(n_i) $$ I want to solve the following optimization problem: \begin{align} \mathrm{maximize} \; \...
3
votes
0answers
248 views

Efficient assembly of finite element matrix(coupled equations case)

I noticed this post, where spalloc and sparse are recommanded for efficient assembly in Matlab. I personally use sparse assembling for simple cases. However, when it comes to the case of coupled PDE, ...
0
votes
1answer
75 views

difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial ...