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

learn more… | top users | synonyms

0
votes
0answers
31 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
31 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
38 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
116 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
63 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 ...
0
votes
0answers
32 views

Convex hull and cartesian Product

Under which conditions, the cartesian product of some closed and bounded polytopes is equivalent to their convex hull?
2
votes
1answer
163 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] + ...
1
vote
1answer
53 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
98 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
110 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 + ...
4
votes
4answers
371 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 ...
1
vote
1answer
59 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
95 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
53 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
146 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 ...
0
votes
0answers
37 views

Linear complementarity problems with inequality (box) constraints

I can find many references and matlab or c++ codes for solving each problem separately. But it is very hard to find one that actually solve both simultaneously on the internet. I am quite sure that ...
4
votes
2answers
208 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
411 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
396 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
79 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. ...
4
votes
3answers
642 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
72 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
2k 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
66 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
334 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
151 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
309 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 ...
5
votes
4answers
852 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 ...
0
votes
2answers
1k views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
1
vote
2answers
156 views

Solving a “generalized” linear programming problem

I need to solve the follwing constrained optimization problem. Is there any MATLAB toolbox which can solve this. minimize $A_1 x$ subject to $A_2 x = 0$ $A_1$ is an $m\times n$ matrix where $m ...
1
vote
0answers
83 views

Cplex C++ Interface: Repeated calls of setQuadCoef are slow. Is there an alternative?

I noticed that repeated calls of the member function setQuadCoef of the class IloObjective can be prohibitively slow. The Cplex ...
2
votes
1answer
347 views

Cplex C++ Interface: How to add many constraints quickly?

I noticed that adding constraints to an IloModel one by one can be prohibitively slow. (I am referring to the construction of the model, not the optimization.) ...
8
votes
1answer
489 views

Least absolute deviations solving using the Barrodale-Roberts-algorithm: Premature termination?

Please excuse the longish question, it just needs some explanation to get down to the actual problem. Those familiar with the mentioned algorithms probably could jump directly to the first simplex ...
1
vote
1answer
157 views

Robust Counterpart of an uncertain LP

Consider the following robust optimization problem: min c'x s.t.: $Ax\geq b \;\;\forall (A,b)\in \mathcal{U}$. Why can the robust counterpart of the problem be written in this form? $min_x{\{ ...
2
votes
2answers
112 views

polynomial time solvability

Consider the following optimization problem: $Min \qquad C^TX$ S.t.: $\qquad AX=0;$ $x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$ $X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; ...
0
votes
1answer
117 views

Semidefinite programming

I have a convex optimization problem that is essentially a linear objective function over some linear constraints and also a semidefinite matrix in the following form: $ M= \left[ ...
4
votes
0answers
148 views

Find maximum distance between elements given constraints on some

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ...
0
votes
0answers
47 views

Lagrangian Duality [duplicate]

Possible Duplicate: Linear programming boundedness Consider the following LP: $\max$ $\sum_{i=1}^N b_i \pi_i$ s.t. $\;\;$ $\pi_i-\pi_j\leq 1 $ $\quad$ for each $(i,j) \in \tilde{A}$ ...
7
votes
2answers
119 views

Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise. The other variables in the linear ...
11
votes
2answers
646 views

Absolute Value in Linear Constraints

I have the following optimization problem where I have absolute value in my constraints: Let $\mathbf{x} \in \mathbb{R}^n$ and $\mathbf{f}_0, \mathbf{f}_1, \ldots, \mathbf{f}_m$ be column vectors of ...
5
votes
1answer
120 views

Linear Programming with constraints of the form $Cx \nless d$ where $C\in R^{m\times n}$

I have an optimization problem that has a linear objective function. The constraints are of the form: $(Ax \leq b) \wedge (Cx \nless d)$. In other words, I have: \begin{align} \min &f^T x ...
3
votes
1answer
299 views

parametric linear programming

I have a linear programming problem min $c^T x$ $Ax\leq b$ However, in my problem, $A$ contains also some variables $y$, e.g. $$A = \begin{pmatrix} y_1 & 4 \\ 3 & y_2 \end{pmatrix}$$ I ...
1
vote
1answer
109 views

Fast Algorithms for solving sparse LP problems

For solving a very sparse LP: {min $cx$: s.t.: $A_{m \times n}x=b$ , $x\geq 0$}, which one of the following algorithms is faster? Logarithmic barrier method Other variants of the interior point ...
2
votes
1answer
63 views

Rational LP to integer LP

In the worst case complexity analysis of all the polynomial algorithms in linear programming such as ellipsoid method and interior point method, there is an assumption that the input data must be ...
0
votes
1answer
261 views

Min-cost flow problem

Consider a min cost flow problem in a directed graph $G=(V, E)$ as follows: (*) Min $\sum {c_{ij}f_{ij}}$ s.t.: $\sum_{j\in out(i)}{f_{ij}} - \sum_{j\in in(i)}{f_{ji}} =b(i)$ for each ...
3
votes
1answer
78 views

Linear programming boundedness

Assume the optimal value of a primal problem is bounded. Is the following statement true? If the primal problem is bounded, then its dual problem is bounded as well.
0
votes
0answers
203 views

Finding a permutation that makes a matrix lower triangular

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
1
vote
2answers
246 views

LP feasibility checking

I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?
1
vote
1answer
172 views

Why isn't every linear program combinatorial?

A linear program (LP) \begin{alignat}{1} & \min_{x} {c}^{T}x, \\ \mathrm{s.t.} & \quad Ax = b, \\ & x \geq 0. \end{alignat} is called combinatorial if the size of entries of matrix $A ...
1
vote
0answers
70 views

Proportional equality constraints

Consider a node $s$. Let's assume that there are three outgoing arcs from node $s$ namely $(s,i)$,$(s,j)$ and $(s,k)$. Corresponding to each of these arcs, there is a flow proportion value $t_{sj}\in ...