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

learn more… | top users | synonyms

3
votes
1answer
42 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) ...
0
votes
0answers
18 views

Determine an algorithm for $LU$ factorization and determine the number of operations

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of $A^{...
1
vote
0answers
16 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
34 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
99 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\...
0
votes
0answers
23 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
44 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
58 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
255 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
92 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
107 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
43 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
36 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
52 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
42 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 - ...
6
votes
1answer
173 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
59 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
37 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, ...
0
votes
0answers
47 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
52 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 }...
0
votes
1answer
57 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
55 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
1answer
105 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
111 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 ...
0
votes
0answers
47 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
68 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
94 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
196 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
73 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 ...
2
votes
1answer
194 views

0,1 binary polynomial programming

Is there a mathematical optimization branch that explicitly tries to optimize this (type) problem? $$\eqalign{ & \min \cr & \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + {J_2}...
1
vote
1answer
280 views

Solving a problem using multiple threads using CLP

Is it possible to run Clp on multiple threads using Julia and JuMP?
0
votes
3answers
211 views

Solving rank deficient systems with cvx

I am using cvx to solve linear programs with constraints of the form $Ax=b,x\ge0$. However the matrix $A$ is rank deficient and cvx returns a warning and finally displays status as 'Infeasible'. Rank ...
2
votes
1answer
460 views

How do I simultaneously minimize two different functions who have the same inputs?

I want to minimize two different functions simultaneously who have the same inputs. The functions are both linear and non-exponential. $$F_1(X_1, X_2) = a_1X_1 + a_2X_2$$ $$F_2(X_1, X_2) = b_1X_1 + ...
7
votes
4answers
2k views

Mathematical optimization software free/openSource

I want to write mathematical optimization software. At university, they taught me how to use AMPL+CPLEX/SCIP/MINOS/Couenne etc.. and that was good enough. But I cannot afford the cost of AMPL for my ...
2
votes
1answer
91 views

Can we express max constraint as a linear constraint?

I have a mathematical program with a constraint involving a maximum function. More specifically, the constraint is: $y = \max\{a_i x_i:1 \leq i \leq n\}$ where $a_i$ are constants and $x_i$ are binary ...
2
votes
1answer
183 views

I have to solve a large binary programming task. Should I avoid branch and bound?

I have to minimize a linear function with respect to variables u which take values [0,1] The number of variables can exceed 10,000 There are thousands of linear inequality constraints I need a ...
0
votes
1answer
109 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
1
vote
2answers
398 views

What sparse linear programming solver it is better to use?

I have the following LP problem: $$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; s.t. \;\;C x \geq 0, \;\; x_{i}^{0} - \varepsilon \...
4
votes
2answers
312 views

Starting at a Given Basic Feasible Solution in the Simplex Method

I have a Simplex problem $ A y \ge b $, where some of the elements of $b$ are positive and some are negative, and thus setting $y = 0$ does not give a basic feasible solution (BFS). By previous work, ...
8
votes
4answers
791 views

Linear programming with matrix constraints

I have an optimization problem that looks like the following $$ \begin{array}{rl} \min_{J,B} & \sum_{ij} |J_{ij}|\\ \textrm{s.t.} & MJ + BY =X \end{array} $$ Here, my variables are matrices $...
4
votes
3answers
2k views

Which algorithm to use for solving an LP with a very large number of variables?

I'm a newbie at modelling and optimization of LPs. My research problem concerns assigning tasks/jobs to virtual machines in a data centre depending on the least energy cost incurred. As you can ...
0
votes
1answer
285 views

Modeling a quadratic constraint with a linear expression

In a problem I am trying to model with a MIP program, the following scenario occurs: I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. ...
5
votes
4answers
3k views

What's the fastest software(open source) to solve mixed integer programming problem

I have a mixed integer programming problem. And I am current using GLPK as my solver. But I found that GLPK is good for Linear Programming problem, but for Mixed Integer programming, it requires much ...
2
votes
1answer
84 views

k-splittable flow problem

The maximum k-splittable s-t flow problem(MkSF) that aims to find a maximum k-splittable flow between a given source and sink node is NP-hard. We do not require the paths to be disjoint, not even ...
4
votes
1answer
3k views

Constrained optimization with max and absolute values in objective function

I would like to find the optimal set $ \{ x_i \} $ given $ L $ and $ \{ a_i \} $ that minimizes the problem below. My first thought was to use linear programming. Is there a transformation that ...
2
votes
1answer
83 views

Which variants of the simplex method are actually used in applications

There are several variants of the simplex method known, which differ by the choice of entering and leaving variables. But neither have I found a reference, which variants are used in which ...
2
votes
1answer
581 views

Update QR decomposition when one column is exchanged

I have got an input series of matrices $A_1, A_2, A_3, \dots $ and the difference between $A_i$ and $A_{i+1}$ is the replacement of one single column. Before i get to know $A_{i+1}$, I have to ...
2
votes
1answer
254 views

Sensitivity analysis of linear program with coin-or clp

I have written a short example to run the simplex algorithm with coin-or Clp, something quite simple like this: ...
-2
votes
3answers
451 views

how to make linear program simplex method use user provided feasible initial point

In some linear program that is hard to find an initial feasible point, simplex method will fail in its phase one algorithm. But we can find such a feasible point through other method such as genetic ...
7
votes
4answers
2k views

How to start the Simplex method from a feasible internal point?

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...