We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integeroptimization based on centerpoints. Furth...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integeroptimization based on centerpoints. Further, we show that algorithms based on centerpoints are "best possible" in a certain sense. Motivated by this, we establish several structural results about this concept and provide efficient algorithms for computing these points.
作者：
Orlin, James B.MIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA
We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n(5) EO + n(6)) time, where EO is the time to evaluate f(S) for some S...
详细信息
ISBN:
(纸本)9783540727910
We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n(5) EO + n(6)) time, where EO is the time to evaluate f(S) for some S subset of V. this improves the previous best strongly polynomial running time by more than a factor of
this paper addresses the energy management of large-scale urban street lighting systems. We propose a multi-stage decision-making procedure that supports the energy manager in determining the optimal energy retrofit p...
详细信息
ISBN:
(纸本)9781509067817
this paper addresses the energy management of large-scale urban street lighting systems. We propose a multi-stage decision-making procedure that supports the energy manager in determining the optimal energy retrofit plan of an existing public street lighting system. the problem statement is based on a quadratic integerprogramming formulation and aims at simultaneously reducing the energy consumption, ensuring an optimal allocation of the retrofit actions, and efficiently using the available budget. the proposed solution relies on a decentralized optimization algorithm that is based on discrete dynamic programming. the methodology is applied to a real street lighting system in the city of Bari, Italy.
the original formal problem definition of financial management optimization of an enterprise at this conjuncture of financing the state defense order is suggested. the problem is shown to belong to the class of NP-har...
详细信息
ISBN:
(纸本)9781509040698
the original formal problem definition of financial management optimization of an enterprise at this conjuncture of financing the state defense order is suggested. the problem is shown to belong to the class of NP-hard problems of the mixed programming. the existing methods for solving this problem are considered and the properties of the program tools developed by the authors for searching for the best solutions are discussed.
the volume contains the papers selected for presentation at IPCO 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the ...
详细信息
ISBN:
(数字)9783540688914
ISBN:
(纸本)9783540688860
the volume contains the papers selected for presentation at IPCO 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the IPCO series of conferences, sponsored by the Mathematical Progr- ming Society, highlights recent developments in theory, computation, and app- cation of integerprogramming and combinatorialoptimization. the ?rst conf- ence took place in 1990; starting from IPCO 1995, the proceedings are published in the Lecture Notes in Computer Science series. the 12 previous IPCO conferences were held in Waterloo (Canada) 1990, Pittsburgh (USA) 1992, Erice (Italy) 1993, Copenhagen (Denmark) 1995 [LNCS 920], Vancouver (Canada) 1996 [LNCS 1084], Houston (USA) 1998 [LNCS 1412], Graz (Austria) 1999 [LNCS 1610], Utrecht (the Netherlands) 2001 [LNCS 2081], Boston (USA) 2002 [LNCS 2337], New York (USA) 2004 [LNCS 2986], Berlin (Germany) 2005 [LNCS 3509], and Ithaca (USA) 2007 [LNCS 4168]. the c- ference is not held in the years when the international Symposium of the Ma- ematical programming Society takes place.
A conic integer program is an integerprogramming problem with conic constraints. Conic integerprogramming has important applications in finance, engineering, statistical learning, and probabilistic integer programmi...
详细信息
ISBN:
(纸本)9783540727910
A conic integer program is an integerprogramming problem with conic constraints. Conic integerprogramming has important applications in finance, engineering, statistical learning, and probabilistic integerprogramming. Here we study mixed-integer sets defined by second-order conic constraints. We describe general-purpose conic mixed-integer rounding cuts based on polyhedral conic substructures of second-order conic sets. these cuts can be readily incorporated in branch-and-bound algorithms that solve continuous conic programming relaxations at the nodes of the search tree. Our preliminary computational experiments withthe new cuts show that they are quite effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs.
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of t...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of the integer lattice.
In this paper we discuss neural network approach for allocation with capacity constraints problem. this problem can be formulated as zero-one integerprogramming problem. We transform this zero-one integerprogramming...
详细信息
In this paper we discuss neural network approach for allocation with capacity constraints problem. this problem can be formulated as zero-one integerprogramming problem. We transform this zero-one integerprogramming problem into an equivalent nonlinear programming problem by replacing zero-one constraints with quadratic concave equality constraints. We propose two kinds of neural network structures based on penalty function method and augmented Lagrangian multiplier method, and compare them by theoretical analysis and numerical simulation. We show that penalty function based neural network approach is not good to combinatorialoptimization problem because it falls in the dilemma whether terminating at an infeasible solution or sticking at any feasible solution, and augmented Lagrangian multiplier method based neural network can alleviate this suffering in some degree.
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show ...
详细信息
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7thinternational IPCO conference on integerprogramming and combinatorialoptimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
暂无评论